#include #define rep(i,n) for (int i = 0; i < n; ++i) #define ALL(c) (c).begin(), (c).end() #define SUM(x) std::accumulate(ALL(x), 0LL) #define MIN(v) *std::min_element(v.begin(), v.end()) #define MAX(v) *std::max_element(v.begin(), v.end()) #define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end()) using namespace std; typedef long long ll; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } const int INF = 1e9; const long long INFL = 1LL<<60; const int mod = 1000000007; ll dp[305][90005]; // i 回移動を行ったときにj段目にいる場合の数 ll sum[305][90005]; int main() { int N, D, K; cin >> N >> D >> K; dp[0][0] = 1; sum[0][0] = 1; for (int i = 0; i < N; i++) { for (int j = 0; j <= K; j++) { if (j - D > 0) dp[i+1][j] = (sum[i][j] - sum[i][j-D]) % mod; else dp[i+1][j] = (sum[i][j] - sum[i][0]) % mod; sum[i][j+1] = sum[i][j] + dp[i][j]; } } /* rep(i, n+1) { rep(j, n*d + 1) { cerr << dp[i][j] << " "; } cerr << endl; } */ cout << dp[N][K] << endl; return 0; }