The Power Mod: Compute a^b mod n

The Royal Cryptographer of Prime City needs to compute massive powers under modular arithmetic. Computing a^b directly would overflow even the kingdom's most powerful brass computer. The solution is fast modular exponentiation ÔÇö squaring the base and halving the exponent at each step. "Binary exponentiation," the Cryptographer says, "reduces O(b) multiplications to O(log b). At each step, if the exponent is odd, multiply the result by the current base. Then square the base and halve the exponent. Take mod at every step to keep numbers small." Given integers a, b, and n, compute a^b mod n using fast exponentiation. Handle b = 0 (result is 1 mod n). Constraints: 0 <= a <= 10^18, 0 <= b <= 10^18, 1 <= n <= 10^9 Input: 2 10 1000 Output: 24 Input: 3 5 7 Output: 5