使用第301题中的规则，考虑如下的设置：

有n个非空的堆，每堆的石子数小于$2^n$且任意两堆的石子数不同。

记W(n)是其中先手必胜态的数量。例如$W(1)=1, W(2)=6, W(3)=168, W(5)=19764360, W(100) \bmod 10^9+7=384777056$。

求$W(10^7) \bmod 10^9+7$。

本题难度:

解答

在此前一系列取石头及其它NIM游戏已提到过，若各堆的石头数此次是$a_1,\ldots,a_n$，那么当且仅当这些数的异或值为0时才是必败态。

把由m个数组成的、符合要求的必败态记作$f_m$。

先从1到$2^n-1$中取m-1个不同的数组成有序序列，这样的取法总数是$(2^n-1)!/(2^n-m)!$，将其记作$g_{m-1}$，并记y为这些数的总异或值。

显然，一般而言只需要令$a_m=y$就可以得到一个长度为m的必败态序列，不过某些特定的y值是不可取的，这包括：

（1）若$y=0$，那么第$a_m$不管怎么取都无法再必败，这样的情况有$f_{m-1}$种。

（2）若y等于$a_1,\ldots,a_{m-1}$中的某个$a_k$，那么第m个数也要等于$a_k$才能使总异或为0，这就不满足任意两堆的石子数不同的要求。这样的情况共有$f_{m-2}\cdot (m-1) \cdot(2^n-1-(m-2))$种，这表示$a_1,\ldots,a_{m-1}$中除$x_k$以外的总异或值为0，这样的情况有$f_{m-2}$种，k有$m-1$个位置可取，每个位置上的值都有$2^n-1-(m-2)$（需要与其它数不同，所以要减去$m-2$）种取法。

因此有 $$f_m=g_{m-1}-f_{m-1}-(2^n-m+1)(m-1)f_{m-2}),$$ 递推计算即得结果$253223948$。

target=10**7
mod=10**9+7
f=[0]*(target+1)
f[0]=1
p=pow(2,target,mod)
g=p-1

for i in range(2,target+1):
    f[i]=(g-f[i-1]-f[i-2]*(i-1)*(p-i+1))%mod
    g=(g*(p-i))%mod

print((g-f[target])%mod)