#include<bits/stdc++.h> #define fst(a,b,c) for(int a=(b);a<=(c);a++) using namespace std; const int N=5e3+100,Mod=1e9+7; int n,k,m,ans; int val[N]; int Add(int x,int y){return (x+y<0)?((x<y)?Add(x+Mod,y):Add(x,y+Mod)):((x+y>=Mod)?x-Mod+y:x+y);} int Mul(int x,int y){return 1ll*x*y%Mod;} int Qp(int x,int y,int z=1){while(y){if(y&1) z=Mul(z,x); x=Mul(x,x); y>>=1;} return z;} int work(int x,int res,int pre){ if(x==k){ ans=Add(ans,val[res]); return 1; } int tmp,cnt=0; fst(i,pre,res/(k-x+1)){ cnt+=(tmp=work(x+1,res-i,i)); ans=Add(ans,Mul(val[i],tmp)); } return cnt; } int main(){ // freopen("math.in","r",stdin); // freopen("math.out","w",stdout); scanf("%d%d%d",&n,&k,&m); fst(i,1,n) val[i]=Qp(i,m); work(1,n,1); printf("%d\n",ans); return 0; }