#include #include using namespace std; using int64 = long long; const int MOD = 1000000007; struct mint { int64 x; mint(const int64 x1=0) { x = x1%MOD; }; mint& operator++(int n) { x+=1; return *this; }; mint& operator--(int n) { x-=1; return *this; }; mint& operator=(int64 n) { x=n%MOD; return *this; }; mint& operator--() {x-=1; return *this; }; 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; } mint& operator/=(const mint a) { return (*this) *= a.inv();} mint operator+(const mint a) const { mint res(*this); return res+=a; } mint operator-(const mint a) const { mint res(*this); return res-=a; } mint operator*(const mint a) const { mint res(*this); return res*=a; } mint operator/(const mint a) const { mint res(*this); return res/=a; } mint inv() const { return pow(MOD-2);} friend ostream& operator<<(ostream &os, const mint a) noexcept { return os << a.x; } constexpr bool operator == (const mint& r) const noexcept { return this->x == r.x; } constexpr bool operator != (const mint& r) const noexcept { return this->x != r.x; } mint pow(long long t) const { if (!t) return mint(1); mint a = pow(t>>1); a*=a; if(t&1) a*= *this; return a; } }; int main() { int n, d, k; cin >> n >> d >> k; vector> dp(n + 1, vector(k + d + 1, 0)); dp[0][0] = 1; for (int i=0; i k-1) continue; dp[i+1][j+1] += dp[i][j]; dp[i+1][j+1+d] -= dp[i][j]; dp[i+1][j+1] += dp[i+1][j]; } } cout << dp[n][k] << endl; }