#include<bits/stdc++.h> #define mod 1000000007 #define ll long long #define N 5005 using namespace std; ll fpow(ll a,ll b){ if(!b) return 1; ll t(fpow(a,b>>1)); if(b&1) return t*t%mod*a%mod; return t*t%mod; } int n,k;ll m,p[N][N],ans; int main(){ scanf("%d%d%d",&n,&k,&m); for(int i(1);i<=n+k;++i) p[i][1]=1; for(int i(1);i<=k;++i) p[0][i]=1; for(int i(1);i<=n;++i){ for(int j(2);j<=k;++j){ p[i][j]=p[i-1][j-1]%mod; if(i>=j) (p[i][j]+=p[i-j][j])%=mod; } } for(int i(1),t;i<=n-k+1;++i){ t=fpow(i,m)%mod; for(int j(1);j<=k&&i*j<=n;++j) ans=(ans+1ll*t*p[n-i*j][k-j])%mod; } printf("%lld\n",ans); return 0; }