#include <iostream> #include <cstdio> #define ll long long using namespace std; int a[5010],n,m,K; ll ans = 0; const ll MOD = 1000000007; ll fp(ll a,ll b) { ll res = 1; while(b) { if(b&1) res = res * a % MOD; a = a * a % MOD; b>>=1; } return res; } void check() { ll sum(0); for(int i(1);i <= K;i++) sum+=a[i]; if(sum != n) return; for(int i(1);i <= K;i++) ans+=fp(a[i],m); return; } void DFS(int k) { if(k == K + 1) { check(); return; } for(int i(a[k - 1] + 1);i <= n;i++) { a[k] = i; DFS(k + 1); } } int main() { cin>>n>>K>>m; DFS(1); cout<<ans % MOD; return 0; }