#include<cstdio> #define rep(a,b,c) for(int c(a);c<=(b);++c) #define drep(a,b,c) for(int c(a);c>=(b);--c) inline int read() { int res=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar(); while(ch<='9'&&ch>='0')res=res*10+(ch^48),ch=getchar();return res; } const int N=1010,Mod=1e9+7;int dp[N][N],g[N][N],n,m,K,pw[N],s[N][N],s2[N][N]; inline void DN(int &x){x>=Mod?x-=Mod:0;} inline int qpow(int a,int b=Mod-2) {int r(1);while(b)b&1?r=1ll*r*a%Mod:0,a=1ll*a*a%Mod,b=b>>1;return r;} int main() { n=read();K=read();m=read();rep(1,n,i)pw[i]=qpow(i,m); pw[0]=0; rep(1,n,i)dp[i][i]=1,g[i][i]=pw[i]; int cnt=0; rep(2,K,i) { rep(i-2,n,j) { rep(1,j,k) { DN(s[j][k]=s[j][k-1]+dp[j][k]); DN(s2[j][k]=s2[j][k-1]+g[j][k]); // printf("cnm %d %d :: %d\n",i,j,s[j][k]); } rep(1,j,k) { // printf("%d %d :: %d %d\n",i,j,j-k,k); // printf("QAQ :: %d %d\n",s[j-k][k],dp[i][j][k]); dp[j][k]=s[j-k][k<j-k?k:j-k]; g[j][k]=s2[j-k][k<j-k?k:j-k]; g[j][k]=(1ll*dp[j][k]*pw[k]+g[j][k])%Mod; // if(!dp[j][k]&&!g[j][k])break; } } } // int cnt=0;rep(1,K,i)rep(1,n,j)rep(1,j,k)if(!dp[i][j][k])++cnt; // rep(1,K,i)rep(1,n,j)rep(1,j,k)printf("(%d,%d,%d) :: %d\n",i,j,k,g[i][j][k]); int ans=0;rep(0,n,k)DN(ans+=g[n][k]);printf("%d\n",ans); } //dp[i][j][k] //<-- 已经分了i个集合，和为j，末尾为k的方案数 //dp[i][j][k]=\sum dp[i-1][j-l][q] (q<=l)