#include <bits/stdc++.h> using namespace std; long long ans;//l long long n,m,k; const long long mod=1000000007; long long f[500012]; long long qqqpow(long long a,long long b, long long p) { if (b==0 )return 1; else if (b%2==1) { return a*qqqpow(a,b-1,p)%p; } else { long long num=qqqpow(a,b/2,p)%p; return num*num%p; } } void dfs (long long il,long long d,long long sum,long long cnt) { if (d==k && sum==n) { ans+=(cnt%mod); //cout<<1; } for (long long i=il; i<=n; i++) { //m if (sum+i<=n) { if (f[i]!=-1) { ; //;//continue;=f[i]=f[i] //f[i]=f[i];else } else { f[i] = qqqpow(i,m,mod); //cout<<i<<endl;//i //cout<<1<<endl; } dfs (i,d+1,sum+i,(cnt+f[i])%mod);//) } } } int main() { cin>>n>>k>>m;//idfsdfsdfsdfsdfs memset(f,-1,sizeof(f)); dfs(1,0,0,0); // for (int i=1; i<=n; i++) // { // cout<<f[i]<<" "<<qqqpow(i,m,mod)<<endl;//endl; // } cout<<ans; return 0; } //