**O(n) time complexity, where n is the length of b.**

Some Hints:

- 1). There are at most 1337 (0~1336) possible results. So increasing b from 1 to an extreme large number, the same results will repetitively show up, as a loop. (
**What is the length of the loop?**) - 2). If the length of loop is c, then
**(a^b)%1337 = (a^(b%c))%1337**. - 3). If (a^b)%x = y, what is (a^(b+1))%x equal to? ------------------------------- (a*y)%x.

```
// O(c): for this problem, c=1337, so...O(1).
int findLoopLength(long long a, long long c)
{
unordered_set<long long> unset; // can also use array of length c
long long t = a%c;
while(unset.find(t)==unset.end())
{
unset.insert(t);
t = (t*a)%c;
}
return unset.size();
}
// return b%c
int bigMod(vector<int>&b, int c)
{
int p = 0;
for(auto d:b)
{
p = (p*10 + d)%c;
}
return p;
}
int superPow(int a, vector<int>& b) {
if(a==1) return 1;
int loop = findLoopLength(a, 1337); // O(1)
int m = bigMod(b, loop); // O(n), where n is the length of b
// costs no more than findLoopLength(...). If the results were stored during the process of finding loop length, this while-loop could be avoided.
long long r = a%1337;
while(m>1)
{
--m;
r = (r*a)%1337;
}
return r;
}
```