#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int N=5e3+10,mod=1000000007; int n,m,p; int ans; int quickpow(int a,int b) { int ret=1; while(b) { if(b&1) ret*=a,ret%=mod; a*=a,a%=mod,b>>=1; } return ret; } int b[N],tot; int cnt[N]; void dfs(int now,int num,int lst,int sum) { if(now==0) { if(!num) { ans+=sum,ans%=mod; } return ; } else if(!num) return ; for(int i=lst;i<=now;i++) b[++tot]=i,dfs(now-i,num-1,i,sum+quickpow(i,m)),--tot; } int main() { scanf("%d %d %d",&n,&p,&m); dfs(n,p,1,0); printf("%d\n",ans); }