#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include using namespace std; using i32 = int_fast32_t; using i64 = int_fast64_t; #define rep(i, n) for (i32 i = 0; i < (i32)(n); i++) #define all(a) (a).begin(),(a).end() #define rall(a) (a).rbegin(),(a).rend() using P = pair; constexpr i64 MAX = 10000000; constexpr i64 MOD = 1000000007; int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); i64 n,d,k; cin >> n >> d >> k; vector> dp(n + 1,vector (k + 1,0)); dp[0][0] = 1; rep(i,n){ rep(j,k){ if(dp[i][j] != 0){ for(i64 l = 1; l < d + 1; l++){ if(j + l <= k){ dp[i + 1][j + l] += dp[i][j]; dp[i + 1][j + l] %= MOD; } } } } } cout << dp[n][k] << endl; }