#include<bits/stdc++.h> #define int long long using namespace std; const int N=5000+5; const int mod=1e9+7; int n,k,m; int p[N][N]; int ans; void get_p(int x,int y) { p[0][0]=1; for(int i=1;i<=x;++i) { for(int j=1;j<=y;++j) { if(i<j)continue; p[i][j]=p[i-1][j-1]+p[i-j][j]; } } } int f(int x,int y,int t) { if(x<=0||y<=0||p[x][y]==0)return 0; if(x-t>0&&y-1>0&&p[x-t][y-1]>0)return (f(x-t,y-1,t)+p[x-t][y-1])%mod; else return 0; } int pow(int x,int y) { if(y==1)return x; if(y==0)return 1; int res=pow(x,y/2); if(y%2==0)return (res*res)%mod; else return (res*res*x)%mod; } signed main() { scanf("%lld%lld%lld",&n,&k,&m); get_p(n,k); for(int i=1;i<=n;++i) { //cout<<f(n,k,i)<<" "<<n<<" "<<k<<" "<<i<<endl; ans=(ans+pow(i,m)*f(n,k,i))%mod; } printf("%lld\n",ans); }