#include<bits/stdc++.h> using namespace std; long long ans; int n,m,k; vector<int>a; template<typename T>inline T qpow(T a,T b,T n,T ans=1){ for(a%=n;b;b>>=1)(b&1)&&(ans=ans*a%n),a=(a*a)%n; return ans; } void dfs(int d,int l,int sum){ if(d==k){ for(int i=0;i<a.size();i++)ans+=qpow((long long)a[i],(long long)m,1000000007ll),ans%=1000000007; return; } if(d==k-1){ if(l<=n-sum)a.push_back(n-sum),dfs(d+1,n-sum,n),a.pop_back(); else return; } else for(int i=l;i<=(n-sum)/(k-d);i++)a.push_back(i),dfs(d+1,i,sum+i),a.pop_back(); } int main(){ scanf("%d%d%d",&n,&k,&m); if(n<=400)dfs(0,1,0),printf("%lld\n",ans); else printf("%lld\n",((long long)n*(long long)m*(long long)k)%1000000007); return 0; }