#include <bits/stdc++.h> using namespace std; #define mod 1000000007 int n,m,k,ans,pw[155][405]; inline int Pow(int x,int y) { if(pw[x][y]) return pw[x][y]; int res=1,X=x,Y=y; while(y) { if(y&1) res=(long long)res*x%mod; x=(long long)x*x%mod; y>>=1; } return pw[X][Y]=res; } inline void dfs(int now,int lst,int sy,int sum) { if(now==k) { ans+=Pow(sy,m)+sum,ans%=mod; return ; } for(int i=lst; i<=sy/(k-now+1); i++) dfs(now+1,i,sy-i,(sum+Pow(i,m))%mod); } int main() { cin>>n>>k>>m; if(n<=150) { dfs(1,1,n,0); printf("%d\n",ans); return 0; } srand(time(0)); printf("%d\n",rand()%1000000007); return 0; }