长度为(n)，字符集为(K)的字符串，两个人博弈：每次要么删去一个字符，要么重新排列（要求排列后的字符串之前没有出现过）。
问先手必胜的字符串的方案数。
(nle 2*10^5,Kle 26)
分析一波：
假如字符串的排列数为偶数：
- 如果存在删去一个字符使得先手必胜，则先手必胜。
- 否则，先手选择重排。后手为了不输也选择重排。循环下去，最后后手不得不删去一个字符。
于是，当字符串排列数为偶数时先手必胜。
假如字符串的排列数为奇数：
- 如果先手选择重排，那就会变成字符串排列数为偶数的情况，后手必胜。
- 先手一定选择删去一个字符。如果删去字符之后排列数为偶数，则后手必胜；所以先手希望删去一个字符使得排列数为奇数。以下证明一定存在删去一个字符使排列数为奇数：(n=sum a_i)，排列数为(frac{n!}{prod a_i!})，删去字符(i)相当于乘(frac{a_i}{n})。找到(lowbit(a_i))最小的(a_i)，显然(lowbit(n)ge lowbit(a_i))，所以(2)的指数不会增加。
于是，当字符串排列数为奇数时，如果(2|n)则后手必胜，否则先手必胜。
综上，发现后手必胜的充要条件为：(2|n)且字符串排列数为奇数。
(n!)中(2)的指数为(sum_xlfloorfrac{n}{2^x} floor)，(prod a_i!)中(2)的指数为(sum_xsum_i lfloorfrac{a_i}{2^x} floor)，现在我们希望它们相等。
显然对于任意(x)，有(lfloorfrac{n}{2^x} floor ge sum_i lfloorfrac{a_i}{2^x} floor)。为了满足上式，左式必须要取等号。
差分一下得(lfloorfrac{n}{2^x} floor -lfloorfrac{n}{2^{x+1}} floor= sum_i lfloorfrac{a_i}{2^x} floor - lfloorfrac{a_i}{2^{x+1}} floor)
也就是说(sum a_i)不进位。
（库默尔定理？？）
然后直接DP：(f_{i,j})表示用了(i)个字符，出现次数或起来为(j)的方案数。转移的时候钦定新的字符必须选没有补的位中最小的那位。
由于转移数不多，所以可以过。
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 250005
#define ll long long
#define mo 1000000009
#define lowbit(x) ((x)&-(x))
ll qpow(ll x,ll y=mo-2){
ll r=1;
for (;y;y>>=1,x=x*x%mo)
if (y&1)
r=r*x%mo;
return r;
}
ll fac[N],ifac[N];
void initC(int n){
fac[0]=1;
for (int i=1;i<=n;++i)
fac[i]=fac[i-1]*i%mo;
ifac[n]=qpow(fac[n]);
for (int i=n-1;i>=0;--i)
ifac[i]=ifac[i+1]*(i+1)%mo;
}
ll C(int m,int n){return fac[m]*ifac[n]%mo*ifac[m-n]%mo;}
int n,K;
ll f[20][N];
int main(){
// freopen("in.txt","r",stdin);
freopen("onmyodo.in","r",stdin);
freopen("onmyodo.out","w",stdout);
scanf("%d%d",&n,&K);
if (n&1){
printf("%lld
",qpow(K,n));
return 0;
}
f[0][0]=1;
initC(max(n,K));
for (int i=0;1<<i+1<=n && i+1<=K;++i){
for (int j=0;j<n;++j)
if (f[i][j]){
int t=lowbit(n^j);
for (int k=n^j^t;1;k=(k-1)&(n^j^t)){
int s=k^t;
(f[i+1][j^s]+=f[i][j]*ifac[s])%=mo;
if (k==0) break;
}
}
}
ll ans=0;
for (int i=0;1<<i<=n && i<=K;++i)
(ans+=fac[n]*f[i][n]%mo*fac[K]%mo*ifac[K-i])%=mo;
printf("%lld
",(qpow(K,n)-ans+mo)%mo);
return 0;
}