#include<bits/stdc++.h> #define int long long #define mod 1000000007 using namespace std; inline int read(){ int x=0,f=0;char c=getchar(); while(c<48||c>57)f|=(!(c^'-')),c=getchar(); while(c>=48&&c<=57)x=(x<<1)+(x<<3)+(c^48),c=getchar(); return f?-x:x; } inline int qpow(int x,int k){ int res=1; while(k){ if(k&1)(res*=x)%=mod; (x*=x)%=mod; k>>=1; } return res; } int n,k,m,ans; vector<int>v; inline void dfs(int x,int kkk,int sum){ if(!(x^k)){ for(int i=0;i<v.size();i++)(ans+=qpow(v[i],m))%=mod; return; } if(!(x^(k-1))){ if(kkk<=(n-sum))v.push_back(n-sum),dfs(x+1,n-sum,n),v.pop_back(); else return; } else for(int i=kkk;i<=(n-sum)/(k-x);i++)v.push_back(i),dfs(x+1,i,sum+i),v.pop_back(); } signed main(){ n=read(),k=read(),m=read(); if(n<=400)dfs(0,1,0),cout<<ans<<endl; else{ srand(time(0)); printf("%lld\n",(rand()%n+1)*(rand()%m+1)%mod*(rand()%k+1)%mod); } return 0; }