/* -*- coding: utf-8 -*- * * 269.cc: No.269 見栄っ張りの募金活動 - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 100; const int MAX_S = 20000; const int MAX_K = 100; typedef long long ll; const ll MOD = 1000000007; /* typedef */ /* global variables */ ll dp[2][MAX_S + 1]; /* subroutines */ /* main */ int main() { int n, s, k; cin >> n >> s >> k; s -= k * n * (n - 1) / 2; if (s < 0) { puts("0"); return 0; } dp[0][0] = 1; int cur = 0, nxt = 1; for (int i = 0; i < n; i++) { memcpy(dp[nxt], dp[cur], sizeof(dp[0])); int ci = n - i, c = ci; while (c <= s) { int maxj = s - c; for (int j = 0; j <= maxj; j++) dp[nxt][j + c] = (dp[nxt][j + c] + dp[cur][j]) % MOD; c += ci; } cur ^= 1, nxt ^= 1; } printf("%lld\n", dp[cur][s]); return 0; }