#include<iostream> #include<cstdio> #include<algorithm> #include<ctype.h> #define int long long using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-')f=-1; ch=getchar(); } while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); } return x*f; } const int N=5005,Mod=1e9+7; int f[N][N],g[N][N],n,m,k; int fac[N]; int qpow(int base,int t) { int ret=1; while(t) { if(t&1) ret=ret*base%Mod; base=base*base%Mod; t>>=1; } return ret; } int mmod(int x) { return x>=Mod?x-Mod:x; } int cal(int x) { int ret=1; for(int i=2; i<=x; i++) ret=ret*i%Mod; return ret; } signed main() { n=read(),k=read(),m=read(); g[0][0]=1; fac[1]=1; for(int i=2; i<=n; i++) fac[i]=qpow(i,m); for(int i=1; i<=k; i++) for(int j=1; j<=n; j++) { for(int l=1; l<=j; l++) g[i][j]=mmod(g[i][j]+g[i-1][j-l]),f[i][j]=(f[i][j]+f[i-1][j-l]+fac[l]*g[i-1][j-l]%Mod)%Mod; } printf("%lld\n",f[k][n]*qpow(cal(k),Mod-2)%Mod); return 0; }