# Question

Your task is to calculate a^b mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example1:

a = 2
b = [3]

Result: 8


Example2:

a = 2
b = [1,0]

Result: 1024


# Solution

What we know:

• $$a^{x + y} = a^x \times a^y$$;
• $$a^{xy} = (a^x)^y$$;
• $$(ab) \% k = ((a \% k)(b \% k)) \% k$$;

Thus, we have

$$a^{10x+y} \% k = (((a^x \% k)^{10} \% k)\times (a^y \% k)) \% k$$.

If we have a function $$f(a, b) = a^b \% k$$, then the above equation can be written as $$a^{10x+y} = (f(f(a, x), 10)\times f(a, y)) \% k$$.

class Solution {
private static final int MOD = 1337;
public int superPow(int a, int[] b) {
a = a % MOD;
if (a == 0) return a;
if (b.length == 0) return 1;
int res = powMod(a, b[0]);
for(int i = 1; i < b.length; i++)
res = (powMod(res, 10) * powMod(a, b[i])) % MOD;
return res;
}

private int powMod(int a, int b) {
if(b == 0) return 1;
a = a % MOD;
int res = a;
for(int i = 1; i < b; i++)
res = res * a % MOD;
return res;
}
}