#include <bits/stdc++.h>
#define int long long

#define F(i, a, b) for (int i = (a); i <= (b); i++)
#define dF(i, a, b) for (int i = (a); i >= (b); i--)
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1000005, M = 2005, inf = 1e16, mod = 1e9 + 7;
int n, m, k, ans, fac[N], ifc[N], inv[N], pw[N], km[M], pwinv2[N], pwk[N];
int qpow(int a, int b = mod - 2) {
	int r = 1;
	for (; b; b >>= 1, a = a * a % mod)
		if (b & 1) r = r * a % mod;
	return r;
}
int C(int n, int m) {
	if (n < m || m < 0) return 0;
	return fac[n] * ifc[m] % mod * ifc[n - m] % mod;
}
void add(int &x, int y) { if ((x += y) >= mod) x -= mod; }

int dp[N];
int solve1(int len) {
	if (!len) return (n - m + 1) * pwk[n - m] % mod;
	int res = 0;
	for (int i = 1; len + (m - len) * i <= n; i++) {
		int coef = i & 1 ? 1 : mod - 1, L = len + (m - len) * i;
		add(res, coef * (n - L + 1) % mod * pwk[n - L] % mod);
	}
	return res;
}
int solve2(int len) {
	int res = 0;
	F(i, 0, (m - len * 2) / 2) {
		add(res, km[m - len - i] * ifc[i] % mod * pwinv2[i] % mod * ifc[m - 2 * len - 2 * i] % mod);
	}
	return res * fac[m - len * 2] % mod;
}
signed main() {
	// freopen("lake.in", "r", stdin);
	// freopen("lake.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> k;
	F(i, 0, 1) fac[i] = ifc[i] = inv[i] = 1;
	pw[0] = pwinv2[0] = pwk[0] = 1;
	F(i, 1, 1e6) {
		pwk[i] = pwk[i - 1] * k % mod;
		pw[i] = pw[i - 1] * 2 % mod;
		pwinv2[i] = pwinv2[i - 1] * (mod + 1 >> 1) % mod;
	} 
	F(i, 2, 1e6) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = inv[mod % i] * (mod - mod / i) % mod;
		ifc[i] = ifc[i - 1] * inv[i] % mod;
	}
	km[0] = 1;
	F(i, 1, m) km[i] = km[i - 1] * (k - i + 1) % mod;
	int cnt = 0;
	F(i, 0, m / 2) {
		if (k < i || k - i < m - 2 * i) continue;
		int r = ifc[i] * ifc[m - 2 * i] % mod;
		dF(j, k, k - i + 1) r = r * j % mod;
		dF(j, k - i, k - i - (m - 2 * i) + 1) r = r * j % mod;
		add(cnt, r * fac[m] % mod * qpow(pw[i]) % mod);
	}
	F(i, 1, m / 2) {
		add(cnt, mod - solve2(i));
		add(ans, solve1(i) * solve2(i) % mod);
	}
	add(ans, solve1(0) * cnt % mod);
	cout << ans << '\n';
	return 0;
}