#include <bits/stdc++.h> using namespace std; inline int QuickPow(long long x,long long y) { long long ans=1; while(y) { if(y&1)ans*=x%1000000007; x*=x%1000000007; y>>=1; } return ans; } int n,m,k,ans; void DFS(int now,int lst,int sy,int sum) { if(now==k) { ans+=QuickPow(sy,m),ans%=1000000007; return; } for(int i=lst; i<=sy/(k-now+1); i++) { ans+=((sum+=QuickPow(i,m))%=1000000007)%=1000000007; DFS(now+1,i,sy-i,(sum+=QuickPow(i,m))); sum-=QuickPow(i,m),(sum+=1000000007)%=1000000007; } } int main() { cin>>n>>k>>m; DFS(1,1,n,0); cout<<ans<<endl; return 0; }