#include <bits/stdc++.h> using namespace std; const int MXN = 5005; const int DVS = 1e9 + 7; int eff[MXN][MXN]; int N, K, M, ans; int pw(int b, int p) { int ans(1); while (p) { if (p & 1) ans = ans * 1LL * b % DVS; b = b * 1LL * b % DVS; p >>= 1; } return ans; } int main() { // freopen("math.in", "r", stdin); // freopen("math.out", "w", stdout); cin >> N >> K >> M; eff[0][0] = 1; for (int i(1); i <= N; ++i) { for (int j(1); j <= i && j <= K; ++j) { eff[i][j] = (eff[i - 1][j - 1] + eff[i - j][j]) % DVS; } } for (int i(1); i <= N; ++i) { int p(pw(i, M)); for (int j(1); j <= K && N - i * j >= K - j; ++j) { ans = (ans + p * 1LL * eff[N - i * j][K - j] % DVS) % DVS; } } cout << ans << endl; return 0; }