#include <bits/stdc++.h> using namespace std; #define ll long long ll n,m,k,ans; const ll mod=1e9+7; vector<int>v; template<typename T> inline void Read(T &x) { x=0; char ch(getchar()); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); } inline ll qp(ll a, ll p) { ll ans=1; while(p) { if(p&1) ans=ans*a%mod; a=a*a%mod; p>>=1; } return ans%mod; } void dfs(int pos, int f, int x) { if(pos==k) { for(int i=0; i<v.size(); i++) ans=(ans+qp(v[i],m))%mod; return ; } if(pos==k-1) { if(f<=n-x) v.push_back(n-x),dfs(pos+1,n-x,n),v.pop_back(); else return ; } else for(int i=f; i<=(n-x)/(k-pos); i++) v.push_back(i),dfs(pos+1,i,x+i),v.pop_back(); } int main() { Read(n),Read(k),Read(m); if(n<=400) dfs(0,1,0),cout<<ans<<endl; else cout<<n%mod*m%mod*k%mod<<endl; return 0; }