#include <bits/stdc++.h> using namespace std; #define ll long long const ll mod=10e9+7; ll n,m,k,cnt,a[1005]; ll ans; long long Qp(ll m,ll n) { n-=1; ll tmp=m; while(n) { if(n&1) { m*=tmp; m%=mod; } tmp=tmp*tmp%mod; n>>=1; } return m; } void dfs(ll sum,ll lst,ll group) { if((group==0&&sum!=0)||(group!=0&&sum==0)) return; if(sum==0&&group==0) { for(int i=1; i<=cnt; i++) ans=(ans+Qp(a[i],m))%mod; } for(int i=lst+1; i<=sum; i++) { a[++cnt]=i; dfs(sum-i,i,group-1); cnt--; } } int main() { scanf("%lld%lld%lld",&n,&k,&m); dfs(n,0,k); cout<<ans%mod<<endl; return 0; }