// https://yukicoder.me/problems/no/269 // status: // tag: [分割数] // ref: http://d.hatena.ne.jp/incognita/20110305/1299344781 // ref: http://drken1215.hatenablog.com/entry/2018/01/16/222843 #define SUBMIT //#define DEBUG #include #include #include #include using namespace std; using ui64 = unsigned long long; using i64 = long long; const int M = 1000000000 + 7; const int MAX_S = 20000; const int MAX_N = 100; // dp[N][S] SのN分割の総数 // dp[n][s] = dp[n][s - n] + dp[n - 1][s] (s >= n) // dp[n][s] = dp[n][s - 1] (otherwise) int dp[MAX_N + 1][MAX_S + 1]; int N, S, K; // 分割数 // nのm分割を求める int solve_partition(int m, int n) { // init memset(dp, 0, sizeof(dp)); dp[0][0] = 1; // partition for (int i = 1; i <= m; ++i) { for (int j = 0; j <= n; ++j) { if (j - i >= 0) dp[i][j] = (dp[i - 1][j] + dp[i][j - i]) % M; else dp[i][j] = dp[i - 1][j] % M; } } return dp[m][n]; } int main() { #ifdef SUBMIT auto& stream = cin; #else stringstream stream(R"(55 2555 1 )"); #endif stream >> N >> S >> K; for (int i = 0; i < N; ++i) S -= i * K; auto ans = solve_partition(N, S); cout << ans << endl; return 0; }