#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
const int N=1e6+10,M=4e3+10,INF=0x3f3f3f3f3f3f3f3f,mod=1000000007;
int n,m,k;
int f[M][M];
int Pk[M],pk[N];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>k;
	f[0][0]=1;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=min(i,k);j++){
			f[i][j]=f[i-1][j-1];
			if(i>=2)f[i][j]=(f[i][j]+f[i-2][j-1]*(i-1)%mod)%mod;
		}
	}
	Pk[0]=1;
	for(int i=1;i<M;i++)Pk[i]=Pk[i-1]*(k-i+1)%mod;
	pk[0]=1;
	for(int i=1;i<N;i++)pk[i]=pk[i-1]*k%mod;
	int sum=0,ans=0;
	for(int c=1;c<=m;c++)sum=(sum+f[m][c]*Pk[c]%mod)%mod;
	for(int w=1;w*2<=m;w++){
		int x=m-w*2,tmp=0;
		for(int c=0;c<=x&&w+c<=k;c++)tmp=(tmp+f[x][c]*Pk[c+w])%mod;
		sum=((sum-tmp)%mod+mod)%mod;
		int co=1,len=m;
		while(len<=n){
			ans=((ans+co*pk[n-len]*tmp%mod*(n-len+1)%mod)%mod+mod)%mod;
			co*=-1;
			len+=x+w;
		}
	}
	ans=(ans+sum*pk[n-m]%mod*(n-m+1)%mod)%mod;
	cout<<ans<<endl;
	return 0;
}