#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include using namespace std; //using namespace atcoder; using ll = long long; using vll = vector; using vvll = vector; using pll = pair; using vpll = vector; using ld = long double; using vld = vector; using vb = vector; #define rep(i, n) for (ll i = 0; i < (n); i++) #ifdef LOCAL #define dbg(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl #else #define dbg(x) true #endif template void chmin(T& a, T b) { a = min(a, b);} template void chmax(T& a, T b) { a = max(a, b);} template ostream& operator<<(ostream& s, const vector& a) { for(auto i : a) s << i << ' '; return s; } constexpr ll INFL = 1LL << 60; constexpr ld EPS = 1e-12; ld PI = acos(-1.0); struct mint { static const long long mod = 1000000007; long long x; mint(long long x = 0) : x((x % mod + mod) % mod) {} mint operator-() const { return mint(-x);} mint& operator+=(const mint& a) {if ((x += a.x) >= mod) x -= mod; return *this;} mint& operator-=(const mint& a) {if ((x += mod - a.x) >= mod) x -= mod; return *this;} mint& operator*=(const mint& a) {(x *= a.x) %= mod; return *this;} friend const mint operator+(const mint& a, const mint& b) { mint ret = a; return ret += b; } friend const mint operator-(const mint& a, const mint& b) { mint ret = a; return ret -= b; } friend const mint operator*(const mint& a, const mint& b) { mint ret = a; return ret *= b; } friend ostream& operator<<(ostream& s, const mint& a) { return s << a.x; } mint pow(long long t) const { if (!t) return 1; mint a = pow(t >> 1); a *= a; if (t & 1) a *= *this; return a; } // for prime mod mint inv() const { return pow(mod - 2);} mint& operator/=(const mint a) { return (*this) *= a.inv();} friend const mint operator/(const mint& a, const mint& b) { mint ret = a; return ret /= b; } }; struct combi { const static long long mod = mint::mod; int n; vector fac, finv, inv; combi(int _n) : n(_n + 1), fac(n, 1), finv(n, 1), inv(n, 1) { for (int i = 2; i < n; ++i) { fac[i] = fac[i - 1] * i; inv[i] =- inv[mod % i] * (mod / i); finv[i] = finv[i - 1] * inv[i]; } }; mint get(int n, int k) { if(n < k) return 0; if(n < 0 || k < 0) return 0; mint ret = fac[n] * finv[k] * finv[n - k]; return ret; } }; void solve() { ll n, s, k; cin >> n >> s >> k; s -= n*(n-1)*k/2; if(s <= 0) { cout << 0 << endl; return; } vector memob(s+1, vb(n+1, false)); using vm = vector; vector memom(s+1, vm(n+1)); function rec = [&](int a, int b) { if(a < 0 || b == 0) return mint(0); else if(a == 0 || b == 1) return mint(1); else if(memob[a][b]) return memom[a][b]; memom[a][b] += rec(a, b-1) + rec(a-b, b); memob[a][b] = true; return memom[a][b]; }; cout << rec(s, n) << endl; return; } int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); cout << fixed << setprecision(15); solve(); }