考虑先手必胜的充要条件。
实际上，只要 \(n\) 为奇数或者本质不同排列为偶数时先手必胜。
\(n\) 为奇数时，先手必胜，答案就是 \(k^n\)。
\(n\) 为偶数时，令 \(a_i\) 为第 \(i\) 个字符出现次数，\(\sum\limits_{i=1}^ka_i=n\)。反面考虑，我们相当于求 \(\dbinom{n}{a_1\ a_2\ ...\ a_k}\) 为奇数的方案数。
根据 Lucas 定理：
\[\dbinom{m}{n}\equiv\prod\limits_{i=0}^q\dbinom{m_i}{n_i}\mod p
\]
其中 \(m=\sum\limits_{i=0}^qp^{i}m_i\)，\(n\) 同理。
显然这里令 \(p\) 为 \(2\)，\(m_i,n_i\in\{0,1\}\)。这告诉我们 \(\dbinom{n}{a_1\ a_2\ ...\ a_k}\) 为奇数，相当于 \(\forall i\neq j,a_i\&a_j=0\)。
考虑一个 dp，\(f_{i,j}\) 表示前考虑 \(i\) 个字符，目前 \(\sum a_i\) 为 \(j\) 的方案数。那么有转移方程：
\[f_{p,l}=\sum\limits_{i\&j=0,i|j=l}f_{p-1,i}\frac{1}{j!}
\]
这东西显然是个子集卷积，预处理 \(g_{|i|,i}=\frac{1}{i!}\) 的子集和，暴力做 \(O(kn\log^2n)\)。
然后你死了，最大的点跑了 13 秒，而且空间爆了。考虑优化。
我们考虑指数生成函数暴力 exp 取 ln 然后就做完了。
其实每次转移的 \(g\) 都是相同的，这让我们想到了快速幂。
借用快速幂的思想，省略每次重复计算 \(f\) 卷 \(g\) 的若干次，复杂度 \(O(n\log^2n\log k)\)。
挺卡常，但这总比多项式好吧。
int main() {
n = read(), k = read(), mod = read();
if (n & 1) return write(qpow(k, n)), 0;
for (S = 1; S <= n; S <<= 1, c++) ;
for (int i = 1; i <= S; i++) pt[i] = pt[i >> 1] + (i & 1);
inv[1] = fac[0] = ifac[0] = g[0][0] = 1;
for (int i = 1; i <= S; i++) {
if (i > 1) inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
fac[i] = 1ll * fac[i - 1] * i % mod, g[pt[i]][i] = ifac[i] = 1ll * ifac[i - 1] * inv[i] % mod;
}
for (int i = 0; i <= pt[n]; i++) fwt(g[i], 1);
for (int i = 0; i < S; i++) f[0][i] = 1;
int ans = qpow(k, n);
while (k) {
if (k & 1) {
for (int i = pt[n]; ~i; i--)
for (int j = 0; j < i; j++)
for (int l = 0; l < S; l++)
Mod(f[i][l], 1ll * f[j][l] * g[i - j][l] % mod);
}
for (int i = pt[n]; ~i; i--) {
if (i) for (int j = 0; j < S; j++) Mod(g[i][j], g[i][j]);
for (int j = 1; j < i; j++)
for (int l = 0; l < S; l++)
Mod(g[i][l], 1ll * g[j][l] * g[i - j][l] % mod);
}
k >>= 1;
}
fwt(f[pt[n]], -1);
write((ans + mod - 1ll * fac[n] * f[pt[n]][n] % mod) % mod);
return 0;
}