The Big Exponent: a^b mod n with Large b and Modular Properties

The kingdom's astronomers have computed a massive exponent b, but they need a^b mod n where b can be astronomically large ÔÇö too large to fit in a standard integer. The Royal Mathematician shows you a trick: if n is prime, Fermat's Little Theorem tells us a^(n-1) Ôëí 1 (mod n), so we can reduce b modulo (n-1). "When the modulus is prime," the Mathematician explains, "we can reduce the exponent modulo (n-1) before computing. This is the power of Fermat's Little Theorem combined with binary exponentiation." Given integers a, b (as a string, potentially up to 10^100000 digits), and a prime n, compute a^b mod n. Use Fermat's Little Theorem to reduce the exponent: b mod (n-1), then binary exponentiation. Constraints: 1 <= a <= 10^18, b has up to 10^5 digits, 2 <= n <= 10^9 and n is prime Input: 2 10 7 Output: 2 Input: 3 100000000000000000000000000000 11 Output: 4