#include<cstdio> #include<iostream> #define ll long long using namespace std; const int N=5005,mod=1e9+7; int n,m,K; ll dp[N][N],f[N][N]; int qsm(int a,int b) { int res=1; for(;b;b>>=1) { if(b&1) res=1ll*res*a%mod; a=1ll*a*a%mod; } return res; } int main() { scanf("%d%d%d",&n,&K,&m); dp[0][0]=1; for(int i=1;i<=n;i++) for(int k=1;k<=K;k++) for(int j=i;j<=n;j++) { f[j][k]=(f[j][k]+f[j-i][k-1]+1ll*qsm(i,m)*dp[j-i][k-1]%mod)%mod; dp[j][k]=(dp[j][k]+dp[j-i][k-1])%mod; } printf("%lld",f[n][K]); return 0; }