E - Everything on It | AtCoder Regular Contest 096

公式解説動画のとおりに実装。

ちなみに22k mod p (pは素数)はフェルマーの小定理より 22k mod (p-1) mod p で求まる。

vector<vi> dp;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
 
    int N, M;
    while (cin >> N >> M) {
        MOD = M;
        dp = vector<vi>(N + 1, vi(N + 1));
        dp[0][0] = 1;
 
        for (int a = 1; a <= N; ++a)for (int b = 0; b <= a; ++b) {
            sadd(dp[a][b], dp[a - 1][b]);
            if (b > 0) {
                sadd(dp[a][b], dp[a - 1][b - 1]);
                sadd(dp[a][b], mul(dp[a - 1][b], b));
            }
        }
 
        vi A(N + 1);
        rep(a, N + 1) {
            MOD = M - 1;
            int p = powm(2, N - a);
            MOD = M;
            int q = powm(2, p);
            rep(b, a + 1) {
                int r = powm(2, (ll)(N - a)*b);
                int s = mul(q, mul(dp[a][b], r));
                sadd(A[a], s);
            }
        }
 
        auto C = combinations(N, M);
 
        int re = 0;
        rep(a, N + 1) {
            int p = mul(C[N][a], A[a]);
            if (a % 2)p = mul(p, -1);
            sadd(re, p);
        }
        cout << re << endl;
    }
}