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`