#include<cstdio> #include<iostream> using namespace std; typedef long long ll; const int N=5e3+10; const ll mod=1e9+7; int n,m,p; ll f[N][N],qzh[N][N]; int quickpow(int a,int b) { int ret=1; while(b) { if(b&1) ret=(1ll*ret*a)%mod; a=(1ll*a*a)%mod,b>>=1; } return ret; } int main() { scanf("%d%d%d",&n,&p,&m); f[0][0]=1; for(int i=1;i<=n;i++) for(int k=1;k<=p;k++) for(int j=i;j<=n;j++) { qzh[j][k]=(qzh[j][k]+qzh[j-i][k-1])%mod; qzh[j][k]+=1ll*quickpow(i,m)*f[j-i][k-1]%mod; f[j][k]=(f[j][k]+f[j-i][k-1])%mod; } printf("%lld",qzh[n][p]); return 0; }