Description

Submission

class Solution {
    const int M = 1337;
    int mem[11][1337];
public:
    int superPow(int a, vector<int>& b) {
        a %= M;
        
        for(int j = 0; j < M; ++j) {
            mem[0][j] = 1;
            for(int i = 1; i < 11; ++i) {
                mem[i][j] = (mem[i-1][j] * j) % M;
            }
        }
        int coeff = 1;
        int cur = a;

        for(; !b.empty(); b.pop_back()) {
            coeff = (coeff * mem[b.back()][cur]) % M;
            
            if(b.size() > 1) cur = mem[10][cur] % M;
            else cur = 1;
        }

        return (coeff * cur) % M;
    }
};

// under mod 1337:
// 213738367^200 = 199^200 = (199^10)^20
// 213738367^201 = 199^201 = 199^1 * 199^200