A rolling checksum repeatedly raises a base to large powers under a modulus. Given three integers a, b, and m, compute (a ** b) mod m, the remainder when a raised to the power b is divided by m.
By convention a ** 0 = 1 for every a (including a = 0). The result must be the non-negative remainder in the range [0, m - 1]. Because b can be enormous, computing a ** b directly is infeasible — reduce modulo m as you go.
Input format
A single line with three space-separated integers a, b, and m.
Output format
A single integer: (a ** b) mod m.
Constraints
- 0 ≤ a ≤ 1000000000
- 0 ≤ b ≤ 1000000000000000
- 1 ≤ m ≤ 1000000000
Note: when m = 1 every remainder is 0.