Three natural numbers x, n, and m are read. Print the value of x^n modulo m, computed using a recursive function that exploits exponentiation by squaring (the number of calls must be of order log2(n)).

Define a recursive function power(x, n, m) that returns (x^n) mod m, using the relation:

power(x, 0, m) = 1 mod m
power(x, n, m) = (power(x, n/2, m))^2 mod m,              if n is even
power(x, n, m) = ((power(x, n/2, m))^2 * x) mod m,        if n is odd

Note: do NOT compute x^n directly and then take modulo (intermediate values can be enormous). Reduce modulo m after every multiplication.