#include <iostream> #include <vector> using namespace std; typedef long long ll; typedef vector<ll> vl; typedef vector<vl> vvl; const ll mod=1e9+7; ll n,k,d; int main(){ cin>>n>>k>>d; // a:=残り数 b:=処理数 ll a=n%(k-1)==0?k-1:n%(k-1),b=(n-a)/(k-1); // コーナーケース if(d==1){ cout<<b<<endl; return 0; } // dp:=通り数 DP:=総和 vvl dp(a+1,vl(b+1)),DP(a+1,vl(b+1)); dp[0][0]=1; for(int i=1;i<=a;i++){ ll x=0,y=0,z=0; for(int j=0;j<=b;j++){ x=(x+dp[i-1][j])%mod; y=(y+DP[i-1][j])%mod; z=(z*d+dp[i-1][j])%mod; dp[i][j]=x; DP[i][j]=(y+z)%mod; } } cout<<DP[a][b]<<endl; }