func_code_string: #include <bits/stdc++.h>   using namespace std;   const int maxn = 2.7e5 + 5;   int m, n, k;   int mod;   int f[19][maxn];   vector<long long> g;   int cnt[maxn];   int upd(const int &x) {     if (x < 0) return x + mod;     if (x >= mod) return x - mod;     return x;   }   void add(int &x, const int &y) { x = upd(x + y); }   int ksm(int x, int k) {     int ans = 1;     while (k) {       if (k & 1) ans = 1ll * ans * x % mod;       x = 1ll * x * x % mod;       k >>= 1;     }     return ans;   }   int jc[maxn], inv[maxn];   void init(int n) {     jc[0] = 1;     for (int i(1), endi(n); i <= endi; i++) jc[i] = 1ll * jc[i - 1] * i % mod;     inv[n] = ksm(jc[n], mod - 2);     for (int i(n - 1), endi(0); i >= endi; i--)       inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;   }   void F(int *f, int n, int h) {     for (int p = 1; p < n; p <<= 1)       for (int i = 0; i < n; i += p << 1)         for (int k(i), endk(i + p - 1); k <= endk; k++) {           add(f[k + p], h * f[k]);         }   }   int l;   vector<long long> operator*(vector<long long> &A, vector<long long> &B) {     static vector<long long> C;     C.clear();     C.resize(l + 1);     for (int i(0), endi(l); i <= endi; i++)       for (int j(0), endj(l - i); j <= endj; j++) C[i + j] += A[i] * B[j];     for (int i(0), endi(l); i <= endi; i++) C[i] %= mod;     return C;   }   vector<long long> pksm(vector<long long> A, int k) {     static vector<long long> C;     C.clear();     C.resize(l + 1);     C[0] = 1;     while (k) {       if (k & 1) C = C * A;       A = A * A;       k >>= 1;     }     return C;   }   int main() {     cin >> n >> k >> mod;     init(n);     if (n & 1) {       cout << ksm(k, n);       return 0;     }     m = 1;     while (m <= n) m <<= 1, l++;     for (int i(0), endi(m - 1); i <= endi; i++) cnt[i] = cnt[i >> 1] + (i & 1);     init(m);     for (int i(0), endi(m - 1); i <= endi; i++) {       f[cnt[i]][i] = inv[i];     }     for (int i(0), endi(l); i <= endi; i++) F(f[i], m, 1);     g.resize(l + 1);     for (int s(0), ends(m - 1); s <= ends; s++) {       for (int i(0), endi(l); i <= endi; i++) g[i] = f[i][s];       g = pksm(g, k);       for (int i(0), endi(l); i <= endi; i++) f[i][s] = g[i];     }     F(f[cnt[n]], m, -1);     cout << upd(ksm(k, n) - 1ll * f[cnt[n]][n] * jc[n] % mod);     return 0;   }   