Quite recently a creative student Lesha had a lecture on trees. After the lecture Lesha was inspired and came up with the tree of his own which he called a -tree.
最近有一個(gè)富有創(chuàng)造力的學(xué)生Lesha聽了一個(gè)關(guān)于樹的講座。在聽完講座之后，Lesha受到了啟發(fā)，并且他有一個(gè)關(guān)于k-tree（k叉樹）的想法。

A k -tree is an infinite rooted tree where:
each vertex has exactly k k children;
each edge has some weight;
if we look at the edges that goes from some vertex to its children (exactly k k edges), then their weights will equal.

k-tree都是無根樹，并且滿足：
每一個(gè)非葉子節(jié)點(diǎn)都有k個(gè)孩子節(jié)點(diǎn)；
每一條邊都有一個(gè)邊權(quán)；
每一個(gè)非葉子節(jié)點(diǎn)指向其k個(gè)孩子節(jié)點(diǎn)的k條邊的權(quán)值分別為1,2,3,...,k。

The picture below shows a part of a 3-tree.

如圖所示：

image

As soon as Dima, a good friend of Lesha, found out about the tree, he immediately wondered: "How many paths of total weight n n (the sum of all weights of the edges in the path) are there, starting from the root of a k k -tree and also containing at least one edge of weight at least d d ?".Help Dima find an answer to his question. As the number of ways can be rather large, print it modulo 1000000007 1000000007 ().

當(dāng)Lesha的好朋友Dima看到這種樹時(shí)，Dima馬上想到了一個(gè)問題：“有多少條從k-tree的根節(jié)點(diǎn)出發(fā)的路上的邊權(quán)之和等于n，并且經(jīng)過的這些邊中至少有一條邊的邊權(quán)大于等于d呢?” 現(xiàn)在你需要幫助Dima解決這個(gè)問題?？紤]到路徑總數(shù)可能會非常大，所以只需輸出路徑總數(shù) mod 1000000007 即可。（1000000007=10^9+7）

輸入格式

A single line contains three space-separated integers: n, k and d().

只有一行數(shù)，n，k，d. (1 <= n, k <= 100; 1 <= d <= k; n, d, k 三者用空格隔開)。

輸出格式

Print a single integer — the answer to the problem modulo1000000007 ().

只有一行，一個(gè)整數(shù)，即輸出路徑總數(shù) mod 1000000007。

樣例輸入

3 3 2

樣例輸出

3

題解

#include<bits/stdc++.h>
#define maxk 105
#define maxn 105
using namespace std;
const long long mod = 1e9+7;
inline char get(){
    static char buf[3000],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,3000,stdin),p1==p2)?EOF:*p1++;
}
inline long long read(){
    register char c=get();register long long f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
    return _*f;
}
long long n,k,d;
long long dp[maxn][3];//第一維記錄不考慮d的情況，第二維記錄考慮d的情況 
long long cas;
int main(){
    //freopen("1.txt","r",stdin);
    n=read();k=read();d=read();//總和等于n，k叉樹，至少一條邊大于等于d 
    for(register long long i=1;i<=n;i++){//i表示當(dāng)前n=i 
        for(register long long j=1;j<=k && j<=i;j++){ 
            cas=i-j;
            bool used_d=0;
            if(j>=d)used_d=1;
            dp[i][1]+=dp[cas][1];//因?yàn)榈谝痪S不考慮d的大小，直接相加即可 
            if(cas==0){
                dp[i][1]++;//無論如何第一維都要加 
                if(used_d)dp[i][2]++;//如果當(dāng)前考慮了d，則讓考慮了d的維度更新 
            }
            else{
                if(used_d)dp[i][2]+=dp[cas][1];//如果目前考慮的d,則之前就不用考慮d了 
                else dp[i][2]+=dp[cas][2];//如果目前沒考慮d，則之前要考慮d 
            }
        }
        dp[i][1]%=mod;
        dp[i][2]%=mod;
    }
    cout<<dp[n][2]%mod;
    return 0;
}