#include <bits/stdc++.h>
using namespace std;

#define QwQ330AwA return 0
#define ll long long

const int mod = 1e9 + 7;
const int N = 3035;
int n, k, q;
ll f[N], g[N], a[N], b[N];
ll inv[N];
ll ksm(ll a, int b) {
	ll ans = 1;
	for (; b; b >>= 1, a = a * a % mod) {
		if (b & 1) ans = ans * a % mod;
	}
	return ans;
}
ll s[N][N];
ll fac[N];

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k >> q;
	if (n <= 3005) {
		ll ans = 0;
		fac[0] = 1;
		for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
		inv[n] = ksm(fac[n], mod - 2);
		for (int i = n; i >= 1; i--) inv[i - 1] = inv[i] * i % mod;
		ll now = 0;
		for (int i = 1; i <= n; i++) {
			now = (now + ksm(i, k)) % mod;
			ans = (ans + now * ksm(q, i) % mod * fac[n] % mod * inv[i] % mod * inv[n - i] % mod) % mod;
		}
		cout << ans;
		return 0;
	}
	f[0] = 1;
	for (int i = 1; i <= k + 2; i++) inv[i] = ksm(mod - i, mod - 2);
	for (int i = 1; i <= k + 2; i++) {
		for (int j = k + 2; j >= 0; j--) {
			f[j + 1] = (f[j + 1] + f[j]) % mod;
			f[j] = f[j] * (mod - i) % mod;
		}
	}
	ll xs = 0;
	for (int i = 1; i <= k + 2; i++) {
		g[0] = f[0];
		for (int j = 0; j <= k + 1; j++) {
			g[j] = g[j] * inv[i] % mod;
			g[j + 1] = (f[j + 1] - g[j] + mod) % mod;
		}
		xs += ksm(i, k);
		xs %= mod;
		ll iv = 1;
		for (int j = 1; j <= k + 2; j++) {
			if (i == j) continue;
			iv = iv * (i - j) % mod;
			iv = (iv + mod) % mod;
		}
		iv = ksm(iv, mod - 2) % mod;
		for (int j = 0; j <= k + 1; j++) {
			a[j] = (a[j] + g[j] * xs % mod * iv % mod) % mod;
		}
	}
	s[0][0] = 1;
	for (int i = 1; i <= k + 1; i++) {
		for (int j = 0; j <= i; j++) {
			s[i][j] = s[i - 1][j] * j % mod;
			if (j) s[i][j] = (s[i][j] + s[i - 1][j - 1]) % mod;
		}
	}
	for (int i = 0; i <= k + 1; i++) {
		for (int j = i; j <= k + 1; j++) {
			b[i] = (b[i] + a[j] * s[j][i] % mod) % mod;
		}
	}
	ll ans = 0;
	ll down = 1;
	for (int i = 0; i <= min(n, k + 1); i++) {
		ans = ans + down * b[i] % mod * ksm(q, i) % mod * ksm(q + 1, n - i) % mod;
		ans %= mod;
		down = down * (n - i) % mod;
	}
	cout << ans;
	QwQ330AwA;
}