【题目描述】：
    小A和小B又想到了一个新的游戏。
    这个游戏是在一个1*n的棋盘上进行的，棋盘上有k个棋子，一半是黑色，一半是白色。
    最左边是白色棋子，最右边是黑色棋子，相邻的棋子颜色不同。
    小A可以移动白色棋子，小B可以移动黑色的棋子，他们每次操作可以移动1到d个棋子。
    每当移动某一个棋子时，这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。
    小A和小B轮流操作，现在小A先移动，有多少种初始棋子的布局会使他胜利呢？
【题目解法】：    
    考虑在一个1*n的棋盘上放置K个棋子，相当于有K+1堆石子，石子数可以为0，总的石子个数为n-K，先手后手在偶数堆上做NimK游戏
    考虑所有放置石子的方案，我们将每一堆石子个数+1，然后变成每一堆的石子个数至少为1
    然后使用隔板法，一共有n+1个石子，因此有n个空隙；要隔成K+1堆，因此选择K个空隙。所以全集为C(n,K)
    考虑NimK游戏，先手必败当且仅当石子数所有二进制位每一位上1的个数取模(d+1)都为0
    我们求出先手必败状态即可
    f[i][j]表示二进制前i位放置了j个石子的方案数
    f[i][j]->f[i+1][k*(d+1)*(1<<i)]*C(K/2,k*(d+1))
    然后我们考虑对于一个合法的奇数堆组合f[15][i]，我们还要考虑上偶数的情况
    现在剩下n-K-i个石子，放在K/2+1堆中，每一堆石子可以为0。
    因此我们同样处理，将每一堆都+1，然后变成n-K-i+K/2，拆成K/2份，因此就是C(n-K-i+K/2,K/2)
    时间复杂度O(15*N*K)

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=10005;
const int M=105;
const long long maxmod=1000000007;
int n,K,d,c[N][M],f[16][N],ans;
inline long long getint()
{
    long long x=0; char c=getchar(); bool flag=false;
    while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
    if (c=='-') flag=true,c=getchar();
    while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
    if (flag) return -x; else return x;
}
inline void updata(int &a,int b)
{
    a=a+b; if (a>=maxmod) a-=maxmod;
}
void init()
{
    n=getint(); K=getint(); d=getint();
    for (int i=0; i<=n; i++) c[i][0]=1;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=min(i,K); j++)
        updata(c[i][j],(c[i-1][j]+c[i-1][j-1])%maxmod);
}
inline int C(int n,int m)
{
    if (m>n-m) m=n-m;
    return c[n][m];
}
void solve()
{
    f[0][0]=1; ans=0;
    for (int i=0; i<15; i++)
        for (int j=0; j<=n-K; j++)
            for (int k=0; k<=n; k++)
            {
                if (k*(d+1)>K/2) break; if (j+k*(d+1)*(1<<i)>n-K) break;
                updata(f[i+1][j+k*(d+1)*(1<<i)],(long long)f[i][j]*C(K/2,k*(d+1))%maxmod);
            }
    for (int i=0; i<=n-K; i++) updata(ans,(long long)f[15][i]*C(n-K-i+K/2,K/2)%maxmod);
    ans=(C(n,K)-ans+maxmod)%maxmod; printf("%d\n",ans);
}
int main()
{
    init();
    solve();
    return 0;
}