Description
小A和小B又想到了一个新的游戏。
这个游戏是在一个1*n的棋盘上进行的，棋盘上有k个棋子，一半是黑色，一半是白色。
最左边是白色棋子，最右边是黑色棋子，相邻的棋子颜色不同。
小A可以移动白色棋子，小B可以移动黑色的棋子，他们每次操作可以移动1到d个棋子。
每当移动某一个棋子时，这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。
小A和小B轮流操作，现在小A先移动，有多少种初始棋子的布局会使他胜利呢？
Input
共一行，三个数，n,k,d。
Output
输出小A胜利的方案总数。答案对1000000007取模。
Sample Input
10 4 2
Sample Output
182
HINT
1<=d<=k<=n<=10000, k为偶数，k<=100。
Solution
我组合计数和$DP$真的是菜的真实……
首先这个题必须加一个限制条件：先手只能向右，后手只能向左，不然下面的做法会被黄学长找出来反例……？QAQ 不过还是能过的我也不知道为什么
首先比较容易发现，因为每个人操作的方向是一定的，所以可以把一对相邻的黑白棋中间的格子数看成一堆石子，那么这个就变成了一个有$k/2$堆的$Nim$游戏。只不过这个$Nim$游戏一次可以取$1 \sim d$堆，也就是$k-Nim$游戏。
$k-Nim$游戏的先手必败态是把每堆石子转换为二进制后，其中每一位上为1的个数和都能被$(d+1)$整除。
感性理解还是挺正确的……具体证明戳这里吧。
然后就可以开始$DP$了。设$f[i][j]$表示$DP$到了二进制的第$i$位，用了$j$个棋子的必败态方案数。
$f[i][j]= \sum f[i-1][j-l \times (d+1) \times 2^i]*C_{k/2}^{l \times (d+1)}$
（这一次用了$l \times (d+1) \times 2^i$个石子，乘组合数是因为从$k/2$堆石子里选出$k \times (d+1)$堆。）
最后答案为$C_n^k-\sum_{i=0}^{n-k}f[15][i] \times C_{n-k/2-i}^{k/2}$
（乘组合数是因为每对棋子在棋盘上的距离确定了，就差每对棋子的排列方式了。）
Code
#include<iostream>
#include<cstdio>
#define N (10009)
#define LL long long
#define MOD (1000000007)
using namespace std; LL n,k,d,p[],C[N][],f[][N]; void Init()
{
p[]=;
for (int i=; i<=; ++i) p[i]=p[i-]<<;
C[][]=;
for (int i=; i<=n; ++i)
for (int j=; j<=min(*k,(LL)i); ++j)
{
(C[i][j]+=C[i-][j])%=MOD;
if (j) (C[i][j]+=C[i-][j-])%=MOD;
}
} int main()
{
scanf("%lld%lld%lld",&n,&k,&d);
Init();
f[][]=;
for (int i=; i<=; ++i)
for (int j=; j<=n-k; ++j)
for (int l=; l*(d+)<=k/&&l*(d+)*p[i-]<=j; ++l)
(f[i][j]+=f[i-][j-l*(d+)*p[i-]]*C[k/][l*(d+)]%MOD)%=MOD;
LL ans=;
for (int i=; i<=n-k; ++i)
(ans+=f[][i]*C[n-k/-i][k/]%MOD)%=MOD;
ans=(C[n][k]-ans+MOD)%MOD;
printf("%lld\n",ans);
}