Power on a clock

A clock with m hours wraps round to 0 after m - 1. Working “on the clock” means keeping only the remainder after dividing by m. Return x to the power n, on a clock of m: that is, (x ** n) % m.

power_mod(3, 4, 5)       # 81 % 5 = 1
power_mod(2, 13, 1000)   # 8192 % 1000 = 192
power_mod(7, 0, 13)      # 1

pow() is switched off for this problem. x ** n works for small n, but for n = 10¹⁸ (a 1 followed by 18 zeros) the number could have about 9 billion billion digits, far more than any computer can store.

Limits

• x is from 0 to 10⁹ (a billion), n from 0 to 10¹⁸ (a billion billion), and m from 1 to 10⁹.