If the modulus weren't 1337 = 7 * 191 but a prime number p, we could use Fermat's little theorem to first reduce the exponent to **e = b % (p-1)** and then compute the result as **a ^{e} % p**. Oh well, we can do it for 1337's prime factors 7 and 191 and then combine the two results with the Chinese remainder theorem. I'll show my derivation of the magic constants 764 and 574 after the solutions below.

I got the solution using Fermat from @Stomach_ache (thanks) and only added the Chinese remainder theorem stuff to adapt it to non-primes like 1337.

## Solution 1: Python "golf"

The helper computes **a ^{b}** modulo the prime

`p`

.```
def superPow(self, a, b):
def mod(p):
return pow(a, reduce(lambda e, d: (10*e + d) % (p-1), b, 0), p) if a%p else 0
return (764 * mod(7) + 574 * mod(191)) % 1337
```

## Solution 2: C++

The helper computes **a ^{b}** modulo the given prime.

```
int superPow(int a, vector<int>& b) {
return (764 * superPow(a, b, 7) + 574 * superPow(a, b, 191)) % 1337;
}
int superPow(int a, vector<int>& b, int prime) {
if (!(a %= prime)) return 0;
int e = 0, mod = prime - 1;
for (int digit : b)
e = (e * 10 + digit) % mod;
int pow = 1;
while (e) {
if (e & 1)
pow = pow * a % prime;
a = a * a % prime;
e >>= 1;
}
return pow;
}
```

## Using the Chinese Remainder Theorem

Let's call **x = a ^{b}**. We want to know

**x % 1337**. The helper function using Fermat already gave us

**u**and

**w**so that

**x % 7 = u**and

**x % 191 = w**. Or put differently,

**x ≡ u (mod 7)**and

**x = w + 191t**for some integer

**t**. Combine these to get

**w + 191t ≡ u (mod 7)**. Subtracting

**w**and multiplying with [191

^{-1}]

_{7}(the multiplicative inverse of 191 modulo 7) we get

**t ≡ (u-w)·[191**.

^{-1}]_{7}(mod 7)We have [191^{-1}]_{7} = [(191%7)^{-1}]_{7} = [2^{-1}]_{7} and one can easily see that the latter is 4, as (2*4)%7=1.

Using that, we have **t ≡ 4(u-w) (mod 7)** or in other words **t = 4(u-w) + 7s** for some integer **s**. Which means:

**x = w + 191t
= w + 191(4(u-w) + 7s)
= 764u - 763w + 1337s
= 764u + (1337-763)w + 1337(s-w)
= 764u + 574w + 1337(s-w)**

So we can compute **x** from **u** and **v** as **x = (764u + 574w) % 1337**, like I have done in my solutions.