func_code_string: #include <bits/stdc++.h>   using namespace std;   const double PI = acos(-1);   const double EPS = 1e-6;   const int INF = 0x3f3f3f3f;   inline int readint() {     int sum = 0;     char c = getchar();     bool f = 0;     while (c <  0  || c >  9 ) {       if (c ==  - ) f = 1;       c = getchar();     }     while (c >=  0  && c <=  9 ) {       sum = sum * 10 + c -  0 ;       c = getchar();     }     if (f) return -sum;     return sum;   }   inline long long readLL() {     long long sum = 0;     char c = getchar();     bool f = 0;     while (c <  0  || c >  9 ) {       if (c ==  - ) f = 1;       c = getchar();     }     while (c >=  0  && c <=  9 ) {       sum = sum * 10 + c -  0 ;       c = getchar();     }     if (f) return -sum;     return sum;   }   const int maxn = 250015;   long long inv[maxn], p[maxn];   void CNumberInit(int MAXNUM, long long mod) {     inv[0] = inv[1] = 1;     p[0] = p[1] = 1;     for (int i = 2; i <= MAXNUM; i++) {       inv[i] = (mod - mod / i) * inv[mod % i] % mod;       p[i] = p[i - 1] * i % mod;     }     for (int i = 2; i <= MAXNUM; i++) inv[i] = inv[i - 1] * inv[i] % mod;   }   long long qmod(long long a, long long b, long long c) {     long long ret = 1;     for (; b; b >>= 1) {       if (b & 1) ret = ret * a % c;       a = a * a % c;     }     return ret;   }   vector<int> megumi;   long long mod;   int k;   long long dp[20][250005];   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);     long long n;     cin >> n >> k >> mod;     CNumberInit(n + 5, mod);     if (n % 2) {       cout << qmod(k, n, mod) << endl;     } else {       for (int i = 2; i <= n; i += 2) {         if ((i & n) == i) megumi.push_back(i);       }       long long ans = 0;       dp[0][n] = 1;       for (int i = 1; i <= min(17, k); i++) {         int tmpans = 0;         for (int j = 0; j < megumi.size(); j++) {           if (!dp[i - 1][megumi[j]]) continue;           int Megumi = megumi[j] & (megumi[j] - 1);           int step = Megumi ^ megumi[j];           for (int k = step; k <= Megumi; k += step) {             if ((k & Megumi) == k) {               dp[i][k] += dp[i - 1][megumi[j]] * p[megumi[j]] % mod * inv[k] %                           mod * inv[megumi[j] - k] % mod;               dp[i][k] %= mod;             }           }           tmpans = (tmpans + dp[i - 1][megumi[j]]) % mod;         }         ans += tmpans * inv[k - i] % mod;       }       ans = ans * p[k] % mod;       ans = qmod(k, n, mod) - ans;       ans = (ans % mod + mod) % mod;       cout << ans << endl;     }     return 0;   }   