#include #include #include #include #include #include #include #include #include #include #include #include #include #include #pragma warning(disable:4996) typedef long long ll; #define MIN(a, b) ((a)>(b)? (b): (a)) #define MAX(a, b) ((a)<(b)? (b): (a)) #define LINF 9223300000000000000 #define LINF2 1223300000000000000 #define INF 2140000000 const long long MOD = 1000000007; //const long long MOD = 998244353; using namespace std; ll dp[90005][305]; void solve() { int n, d, K; scanf("%d%d%d", &n, &d, &K); int i,j,k; dp[0][0] = 1; for (k = 0; k < n; k++) { vector plus(K + 2); for (i = 0; i < K; i++) { int tmp = MIN(d + i, K); plus[tmp+1] = (plus[tmp+1] - dp[i][k]+MOD) % MOD; plus[i + 1] = (plus[i + 1] + dp[i][k]) % MOD; } int p; for (p = 0; p <= K; p++) { if (p == 0) dp[p][k + 1] = plus[p]; else dp[p][k + 1] = (dp[p-1][k + 1] + plus[p])%MOD; } } printf("%lld\n", dp[K][n]); return; } int main(int argc, char* argv[]) { #if 1 solve(); #else int T; scanf("%d", &T); while(T--) { solve(); } #endif return 0; }