Binary Exponentiation

Practice this coding question on Coding Gurukul.

Problem statement

For each query a b m, compute a raised to the power b, modulo m, using binary exponentiation. Use repeated squaring instead of multiplying a by itself b times. Reduce intermediate results modulo m. Define a^0=1, including 0^0. If m=1, the answer is always 0. Use integer arithmetic and O(log(b+1)) time per query. Signed 64-bit intermediate products are sufficient for the given bounds. Worked example 2^10=1024, so its remainder modulo 1000 is 24. 5^0 modulo 7 is 1. Any value modulo 1 is 0.

Input format

First line: q. Next q lines: a b m.

Output format

Print one modular power per line.

Constraints

1 <= q <= 10000; 0 <= a <= 10^9; 0 <= b <= 10^18; 1 <= m <= 10^9.

Sample input

3
2 10 1000
5 0 7
9 9 1

Sample output

24
1
0

Sign in to run or submit a solution in C++, Java or Python.