#include <bits/stdc++.h> using namespace std; const int mod = 1e9+7; int n,m,k,ans,p[5010]; int qsm(int x,int y) { int ret = 1; while(y) { if(y & 1) ret = 1LL * ret * x % mod; x = 1LL * x * x % mod; y >>= 1; } return ret; } int M(int x) { return x < mod ? x : x - mod; } void dfs(int x,int sum,int lst,int s) { if(x == 1) { ans = M(ans + M(s + p[sum])); return ; } for(int i = lst; i <= sum / x; i++) dfs(x - 1,sum - i,i,M(s + p[i])); } int read() { char ch = getchar(); int ret = 0,f = 1; while(ch == ' ' || ch == '\n') ch = getchar(); while(ch == '-') { f *= -1; ch = getchar(); } while('0' <= ch && ch <= '9') { ret = ret * 10 + ch - '0'; ch = getchar(); } return f * ret; } int main() { n = read(),k = read(),m = read(); for(int i = 1; i <= n; i++) p[i] = qsm(i,m); dfs(k,n,1,0); printf("%d\n",ans); return 0; }