#include <bits/stdc++.h> #define ll long long using namespace std; const int maxn=5005; const ll mod=1e9+7; ll p[maxn][maxn]; ll Pow[maxn]; int n,k,m; ll qpow(ll a,ll b){ ll ret=1;while(b){ if(b&1) ret=ret*a%mod; a=a*a%mod;b>>=1; }return ret; } int main(){ scanf("%d%d%d",&n,&k,&m); for(int i=1;i<=n;i++) Pow[i]=qpow(i,m); p[0][0]=1; for(int i=1;i<=n;i++){ for(int j=1;j<=k;j++){ if(i>=j) p[i][j]+=p[i-j][j]; p[i][j]+=p[i-1][j-1]; p[i][j]=p[i][j]%mod; } } ll ans=0; for(int i=1;i<=n;i++){ ll cnt=0; for(int j=1;j*i<=n&&j<=k;j++){ cnt+=p[n-j*i][k-j]; cnt=cnt%mod; } ans+=cnt*Pow[i]; ans=ans%mod; } printf("%lld",ans); }