/*
60 + 0 + 100 + 64 = 224.
*/

#include <bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define L(i, j, k) for (int i = (j); i <= (k); i++)
#define R(i, j, k) for (int i = (j); i >= (k); i--)
#define pb push_back
#define pii pair<int, int>
inline int read()
{
	int sum = 0, nega = 1;
	char ch = getchar();
	while (ch > '9'||ch < '0')
	{
	    if (ch == '-') nega = -1;
		ch = getchar();
	}
	while (ch <= '9' && ch >= '0') sum = sum * 10 + ch - '0', ch = getchar();
	return sum * nega;
}
const int N = 4009, M = 2e6 + 9, mod = 1e9 + 7, inv2 = (mod + 1) / 2;
inline void add(int &x, int y) {x = (x + y) % mod;}
inline void del(int &x, int y) {x = (x - y + mod) % mod;}
inline int Pow(int x, int y) 
{
	int res = 1, base = x % mod;
	while(y) 
	{
		if(y & 1) res = res * base % mod;
		base = base * base % mod; y >>= 1; 
	} return res; 
}
int tt[N]; 
int n, m, k, ans, C[N][N], jc[N], nw, pown[M]; 
inline int f(int x, int y) 
{
	if(x == 0 && y == 0) return 1;
	if(y <= (x - 1) / 2) return 0;
	if(y <= 0) return 0; 
	int res = 0; 
	tt[0] = 1; 
	L(i, 1, x) tt[i] = tt[i - 1] * (y - i + 1) % mod * Pow(i, mod - 2) % mod;  
	L(i, 0, x / 2) 
	{
		int tmp = tt[x - i] * C[x - i][i] % mod; 
		tmp = tmp * jc[x] % mod; tmp = tmp * Pow(inv2, i) % mod;
		res = (res + tmp) % mod;  
	}
	return res; 
}
signed main()
{
	n = read(), m = read(), k = read(); pown[0] = 1; 
	L(i, 1, n) pown[i] = pown[i - 1] * k % mod; 
	L(i, 0, m) C[i][i] = C[i][0] = 1;
	jc[0] = 1;
	L(i, 1, m) jc[i] = jc[i - 1] * i % mod;  
	L(i, 1, m) 
		L(j, 1, i - 1) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod; 
	ans = (ans + f(m, k) * Pow(k, n - m) % mod * (n - m + 1) % mod) % mod; 
	nw = 1; 
	L(i, 1, m / 2) 
	{
		nw = nw * (k - i + 1) % mod;
		int tt = f(m - i * 2, k - i) * nw % mod, sum = 0; 
		L(j, 2, 1e9) 
		{
			int w = m + (m - i) * (j - 1); 
			if(w > n) break; 
			if(j % 2 == 0) sum = (sum - pown[n - w] * (n - w + 1) % mod + mod) % mod; 
			else sum = (sum + pown[n - w] * (n - w + 1) % mod) % mod; 
		}
		ans = (ans + sum * tt % mod) % mod; 
	}
	ans = (ans % mod + mod) % mod; 
	cout << ans << endl; 
	return 0;
}