#include using namespace std; template using min_priority_queue = priority_queue,greater>; template void outvec(vector &v){ bool b = false; for(auto i : v){ if(b) cout << " "; else b = true; cout << i; } cout << endl; } template void invec(vector &v){ for(auto &i : v){ cin >> i; } } template bool chmin(T &a, const T& b) { if (a > b) { a = b; // aをbで更新 return true; } return false; } template bool chmax(T &a, const T& b) { if (a < b) { a = b; // aをbで更新 return true; } return false; } template T exEuclid(T a, T b, T &x, T &y){ T d = a; if(b != 0){ d = exEuclid(b, a%b, y, x); y -= (a/b)*x; } else{ x = 1; y = 0; } //cout << a << " * " << x << " + " << b << " * " << y << " = " << d << endl; return d; } int64_t mod; struct modint{ int64_t n; int64_t p; modint(){ n = 0; p = mod; } modint(int64_t a){ if(a <= -mod) a %= mod; else if(a >= mod) a %= mod; if(a < 0) a += mod; n = a; p = mod; } modint(int64_t a, int64_t q){ if(a <= -q) a %= q; else if(a >= q) a %= q; if(a < 0) a += q; n = a; p = q; } modint pow(int64_t a){ if(a <= 1-p) a %= p-1; else if(a >= p-1) a %= p-1; if(a < 0) a += p-1; modint rtn; if(n == 0) { rtn.n = 0; return rtn; } if(n == 1) { rtn.n = 1; return rtn; } if(a == 0) { rtn.n = 1; return rtn; } if(a == 1) { rtn.n = n; return rtn; } int64_t b = a/2; int64_t c = a%2; rtn = pow(b); rtn *= rtn; if(c){ rtn *= modint(n); } return rtn; } bool operator==(modint other){ return n == other.n && p == other.p; } bool operator!=(modint other){ return !(n == other.n && p == other.p); } modint operator+(modint other){ modint rtn(n+other.n, p); return rtn; } modint operator-(modint other){ modint rtn(n-other.n, p); return rtn; } modint operator*(modint other){ modint rtn(n*other.n, p); return rtn; } modint operator/(modint other){ int64_t x, y, d; d = exEuclid(other.n, p, x, y); int64_t rtn = x*n; if(d > 1) rtn /= d; return modint(rtn); } void operator+=(modint other){ n += other.n; if(n >= p) n %= p; } void operator-=(modint other){ n -= other.n; if(n < 0) n += p; } void operator*=(modint other){ n *= other.n; if(n >= p) n %= p; } void operator/=(modint other){ int64_t x, y, d; d = exEuclid(other.n, p, x, y); n *= x; if(d > 1) n /= d; if(n <= p || p <= n) n %= p; if(n < 0) n += p; return; } void operator++(){ n++; if(n == p) n = 0; return; } void operator--(){ n--; if(n == -1) n = p-1; return; } }; vector fact_mod_v; vector inv_fact_mod_v; modint comb_mod(int64_t n, int64_t m){ if(n < 0 || m < 0 || m > n) return 0; modint rtn = fact_mod_v[n]*inv_fact_mod_v[m]*inv_fact_mod_v[n-m]; return rtn; } modint comb_mod_small(int64_t n, int64_t m){ if(m < mod){ return comb_mod(n%mod, m); } return comb_mod_small(n/mod, m/mod)*comb_mod(n%mod, m%mod); } void init_fact(int64_t n){ fact_mod_v.resize(n+1,0); inv_fact_mod_v.resize(n+1,0); for(int64_t i = 0; i <= n; i++){ if(i == 0){ fact_mod_v[i] = modint(1); } else{ fact_mod_v[i] = modint(i*fact_mod_v[i-1].n); } //cout << i << endl; } for(int64_t i = min(n, mod-1); i >= 0; i--){ if(i == min(n, mod-1)){ inv_fact_mod_v[i] = modint(fact_mod_v[i]).pow(-1); } else{ inv_fact_mod_v[i] = modint(inv_fact_mod_v[i+1].n*(i+1)); } //cout << i << endl; } } template struct monoid_plus{ T val; monoid_plus(){ ; } monoid_plus(T x){ val = x; } monoid_plus e(){ return monoid_plus(0); } monoid_plus operator*(monoid_plus other){ return monoid_plus(val + other.val); } }; template struct segtree{ int sz; vector dat; segtree(){ ; } segtree(int n){ sz = 1; while(sz <= n) sz *= 2; dat.resize(2*sz-1, monoid().e()); } void update(int k, monoid a){ k += sz-1; dat[k] = a; while(k > 0){ k = (k-1)/2; dat[k] = dat[2*k+1]*dat[2*k+2]; } } void plus(int k, monoid a){ update(k, get(k, k+1)*a); } //[a,b) monoid get(int a, int b){ return sub_get(a, b, 0, 0, sz); } monoid sub_get(int a, int b, int k, int l, int r){ if(r <= a || b <= l) return monoid().e(); if(a <= l && r <= b) return dat[k]; monoid vl = sub_get(a, b, 2*k+1, l, (l+r)/2); monoid vr = sub_get(a, b, 2*k+2, (l+r)/2, r); return vl*vr; } }; void yn(bool b){ if(b) cout << "Yes" << endl; else cout << "No" << endl; } bool debug; bool randomInput; bool debugOutput; int numOfTestCase; using ans_type = int; void input(){ if(numOfTestCase > 1){ ; } if(randomInput){ } else{ } return; } void output_input(){ ; } ans_type calc(){ mod = 1'000'000'007; int N, S, K; cin >> N >> S >> K; int M = S - N * (N - 1) / 2 * K; if(M < 0){ cout << 0 << endl; return 0; } vector> dp(N+1, vector(M+1, 0)); dp[0][0] = 1; //int cnt = 0; for(int i = 0; i < N; i++){ for(int j = 0; j <= M; j++){ for(int k = 0; j+k <= M; k += N-i){ dp[i+1][j+k] += dp[i][j]; //cnt++; } } for(int j = 0; j <= M; j++) dp[i+1][j] %= mod; } cout << dp[N][M] << endl; //cout << cnt << endl; /*for(auto i : dp){ for(auto j : i){ cout << j.n << " "; } cout << endl; }*/ return ans_type(); } ans_type calc_simple(){ return ans_type(); } void output(ans_type ans){ return; } int main(){ debug = 0; randomInput = 0; debugOutput = 0; numOfTestCase = 1; srand(time(NULL)); cout << fixed << setprecision(12); if(numOfTestCase == 0) cin >> numOfTestCase; if(debug){ for(int i = 0; i < numOfTestCase; i++){ input(); ans_type ans = calc(); ans_type ansSimple = calc_simple(); if(ans != ansSimple){ output_input(); output(ans); output(ansSimple); } } } else{ for(int i = 0; i < numOfTestCase; i++){ input(); output(calc()); } } return 0; }