222. Power With a Modulus
Print a raised to the power b, modulo m.
a^b itself is astronomically large here and must never be computed. Instead
take the remainder at every step, which is valid because
(x * y) mod m = ((x mod m) * (y mod m)) mod m
Multiplying a by itself b times is a billion multiplications. Halving the
exponent instead makes it about thirty:
a^b = (a^(b/2))^2 when b is even
a^b = a * (a^(b-1)) when b is odd
Compute the half ONCE and square it. Writing it out twice as a product of two identical recursive calls undoes the whole saving.
Constraints - `0 ≤ a ≤ 1000000000` - `0 ≤ b ≤ 1000000000` - `1 ≤ m ≤ 1000000000`
Input
A single line containing three integers a, b and m.
Output
Print one integer, the value of a to the power b, modulo m.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.