1337 only has two divisors 7 and 191 exclusive 1 and itself, so judge if `a`

has a divisor of 7 or 191, and note that 7 and 191 are prime numbers, `phi`

of them is itself - 1, then we can use the Euler's theorem, see it on wiki https://en.wikipedia.org/wiki/Euler's_theorem, it's just Fermat's little theorem if the mod `n`

is prime.

see how 1140 is calculated out:

phi(1337) = phi(7) * phi(191) = 6 * 190 = 1140

**optimized solution update at 2016-7-12**

Today, seeing @myanonymos 's comments, and I find several days ago I AC it just by fortunate coincidence, it's not the best solution. now I get a better idea.

(1) Firstly, if `a`

has both divisor 7 and 191, that's `a % 1337 == 0`

, answer is 0.

(2) Then if `a`

has neither divisor 7 nor 191, that's a and 1337 are coprime, so **a ^{b} % 1337 = a^{b % phi(1337) } % 1337 = a^{b % 1140 } % 1337**.

(3) Finally, `a`

could has either divisor 7 or 191, that's similar.

Let it be 7 for example.

Let **a = 7 ^{n}x**

and let

**b = 1140p + q**, where

**0 < q <= 1140**

then:

**a ^{b} % 1337**

**= ((7**

^{n}x)^{b}) % 1337**= (7**

^{nb}x^{b}) % 1337**= ( (7**

^{nb}% 1337) * (x^{b}% 1337) ) % 1337**= ( (7**

^{1140np + nq}% 1337) * (x^{1140p + q}% 1337) ) % 1337now note x and 1337 are coprime, so

**= ( (7 ^{1140np + nq} % 1337) * (x^{q} % 1337) ) % 1337**

**= ( 7 * (7**

^{1140np + nq - 1}% 191) * (x^{q}% 1337) ) % 1337note 7 and 191 are coprime too, and 1140 is a multiple of 190, where 190 = phi(191). What's more we should assure that q != 0, if b % 1140== 0, then let b = 1140. so

**= ( 7 * (7 ^{nq - 1} % 191) * (x^{q} % 1337) ) % 1337**

**= ( (7**

^{nq}% 1337) * (x^{q}% 1337) ) % 1337**= (7**

^{nq}x^{q}) % 1337**= ((7**

^{n}x)^{q}) % 1337**= (a**

^{q}) % 1337now you see condition (2) and (3) can be merged as one solution, if you take care of when `b % 1440 == 0`

, and let `b += 1140`

. Actually (1) can be merged too, but not efficient.

new code:

C++:

```
int superPow(int a, vector<int>& b) {
if (a % 1337 == 0) return 0; // this line could also be removed
int p = 0;
for (int i : b) p = (p * 10 + i) % 1140;
if (p == 0) p += 1140;
return power(a, p, 1337);
}
int power(int x, int n, int mod) {
int ret = 1;
for (x %= mod; n; x = x * x % mod, n >>= 1) if (n & 1) ret = ret * x % mod;
return ret;
}
```

java:

```
public int superPow(int a, int[] b) {
if (a % 1337 == 0) return 0;
int p = 0;
for (int i : b) p = (p * 10 + i) % 1140;
if (p == 0) p += 1440;
return power(a, p, 1337);
}
public int power(int a, int n, int mod) {
a %= mod;
int ret = 1;
while (n != 0) {
if ((n & 1) != 0) ret = ret * a % mod;
a = a * a % mod;
n >>= 1;
}
return ret;
}
```

Actually, if p == 0 or not, we can always let p += 1140, it doesn't matter.

one line python:

```
def superPow(self, a, b):
return 0 if a % 1337 == 0 else pow(a, reduce(lambda x, y: (x * 10 + y) % 1140, b) + 1140, 1337)
```

**will this be the best solution?**

p.s.

I have testcases that the system missed

574

[1,1,4,0]

764

[1,1,4,0]

in this case if I remove this line of code `if (p == 0) p += 1140;`

, it will get wrong answer, but also can get AC on OJ.

and I found thar 574 * 574 % 1337 = 574, 764 * 764 % 1337 = 764, how interesting!