MathRecursionBinary Exponentiation
Compute a raised to the power b, modulo m, where b can be as large as 10^18. Multiplying a by itself b times is impossible, so use fast exponentiation.
Input
A single line with three integers a, b and m.
Output
Print (a^b) mod m.
Constraints
0 <= a <= 10^9 0 <= b <= 10^18 1 <= m <= 10^9 + 7
Example 1
Input
2 10 1000
Output
24
2^10 = 1024, and 1024 mod 1000 = 24.