#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

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

const int MAXN = 1e6;
const int MAXM = 2000;

const int MOD = 1e9+7;
struct mint
{
	int x;
	mint() : x(0) {}
	mint(int _x) : x(_x) {}
	mint operator + (int ot) const { return x+ot>=MOD ? x+ot-MOD : x+ot; }
	mint operator - () const { return x ? MOD-x : 0; }
	mint operator - (int ot) const { return x<ot ? x+MOD-ot : x-ot; }
	mint operator * (int ot) const { return 1ll*x*ot%MOD; }
	mint operator += (int ot) { return *this=*this+ot; }
	mint operator -= (int ot) { return *this=*this-ot; }
	mint operator *= (int ot) { return *this=*this*ot; }
	operator int() { return x; }
};

mint mpow(mint a, int x)
{
	mint ret=1;
	while(x)
	{
		if(x&1) ret*=a;
		a=a*a; x>>=1;
	}
	return ret;
}
mint inv(mint x) { return mpow(x, MOD-2); }

int N, M, K;
mint dp[MAXM+10][MAXM+10];
mint powK[MAXN+10], ans;

mint f(int M, int K)
{
	if(K<0) return 0;
	mint ncr=1;
	mint ret=0;
	for(int i=0, j=1; i<=M; i++)
	{
		if((M+i)%2) continue;
		for(; j<=(M+i)/2; j++)
		{
			if(K-j+1>=0) ncr*=(K-j+1);
		}
		ret+=dp[M][i]*ncr;
	}
	return ret;
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
	
	scanf("%d%d%d", &N, &M, &K);

	powK[0]=1;
	for(int i=1; i<=N; i++) powK[i]=powK[i-1]*K;

	dp[0][0]=1;
	for(int i=0; i<=M; i++)
	{
		for(int j=0; j<=i; j++)
		{
			if(j) dp[i+1][j-1]+=dp[i][j]*j;
			dp[i+1][j+1]+=dp[i][j];
		}
	}

	mint val=f(M, K);

	mint ncr=1;
	for(int i=1; i<=M/2; i++)
	{
		if(K-i+1>=0) ncr*=mint(K-i+1);
		mint g=ncr*f(M-i-i, K-i);
		int y=M-i;
		mint val2=0;
		for(int t=0; t*y<=N-M; t++)
		{
			if(t%2==0) val2+=powK[N-M-t*y]*(N-M-t*y+1);
			else val2-=powK[N-M-t*y]*(N-M-t*y+1);
		}
		ans+=val2*g;
		val-=g;
	}
	ans+=mint(N-M+1)*powK[N-M]*val;
	printf("%d\n", (int)ans);
}