#include<iostream> #include<cstdio> #define mod 1000000007 using namespace std; int n,m,k; int f[5005][5005],c[5005][5005]; int g[5005][5005],d[5005][5005]; int pw[5005],ans; int add(int x,int y){ if((x+=y)>=mod) x-=mod; return x; } int qp(int x,int y){ int res=1; while(y){ if(y&1) res=1ll*res*x%mod; x=1ll*x*x%mod; y>>=1; } return res; } int main(){ scanf("%d%d%d",&n,&k,&m); for(int i=1;i<=n;i+=1) pw[i]=qp(i,m); for(int p=1;p<=k;p+=1){ for(int i=n;i>=0;i-=1){ if(p==1&&i==n) d[i][0]=1; else d[i][0]=0; for(int j=1;j*(k-p)<=i&&j<=n;j+=1){ g[i][j]=add(g[i][j-1],f[i][j]); d[i][j]=add(d[i][j-1],c[i][j]); } } for(int i=n;i>=0;i-=1){ for(int j=1;j*(k-p)<=i&&j<=n;j+=1){ f[i][j]=add(g[i+j][j],1ll*d[i+j][j]*pw[j]%mod); c[i][j]=d[i+j][j]; if(i==0) ans=add(ans,f[i][j]); } } } printf("%d\n",ans); return 0; }