#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int MOD = 1000000007; int main(){ int n,d,k; cin >> n >> d >> k; vector> dp(n+1,vector(k+1,0)); //dp[i][j]:=i回の移動でj段目にたどり着く移動方法の数 vector sum(k+1,1); for(int i = 0;i < n;i++){ for(int j = 1;j <= k;j++){ if(j-d-1 < 0)dp[i+1][j] = sum[j-1]; else dp[i+1][j] = (sum[j-1] - sum[j-d-1] + MOD) % MOD; } sum[0] = dp[i+1][0]; for(int j = 1;j <= k;j++){ sum[j] = (dp[i+1][j] + sum[j-1]) % MOD; } } cout << dp[n][k] << endl; }