The Euler's Theorem: Reduce Big Exponents for Any Modulus

In the Advanced Mathematics Academy of Prime City, the Professor teaches Euler's theorem ÔÇö a generalization of Fermat's Little Theorem. While Fermat requires the modulus to be prime, Euler's theorem works for any modulus: a^¤å(n) Ôëí 1 (mod n) when gcd(a, n) = 1. "This means we can reduce any massive exponent b modulo ¤å(n)," the Professor says. "Compute a^b mod n as a^(b mod ¤å(n)) mod n, when gcd(a,n) = 1. This is the key to efficient modular exponentiation for arbitrary moduli." Given a, b (as a string up to 10^5 digits), and n, compute a^b mod n. If gcd(a, n) = 1, use Euler's theorem to reduce the exponent. Otherwise, use binary exponentiation directly (b may be large but n is small enough). Constraints: 1 <= a <= 10^18, b up to 10^5 digits, 1 <= n <= 10^9 Input: 3 100 10 Output: 1 Input: 2 10 7 Output: 2