// 私は猫です

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define dF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) (x&(-x))
#define HH printf("\n")
#define eb emplace_back
#define poly vector<int>
#define SZ(x) ((int)x.size())
using namespace std;
template<typename T>inline void chkmax(T &x,const T &y){ x=std::max(x,y); }
template<typename T>inline void chkmin(T &x,const T &y){ x=std::min(x,y); }
const int mod=1e9+7,maxn=500005;
inline int qpow(int x,ll y){
	int rt=1;
	for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) rt=1ll*rt*x%mod;
	return rt;
}
inline void inc(int &x,const int y){ x=(x+y>=mod)?(x+y-mod):(x+y); }
inline void dec(int &x,const int y){ x=(x>=y)?(x-y):(x+mod-y); }
inline void mul(int &x,const int y){ x=1ll*x*y%mod; }
inline int add(const int x,const int y){ return (x+y>=mod)?(x+y-mod):(x+y); }
inline int sub(const int x,const int y){ return (x>=y)?(x-y):(x+mod-y); }
inline int prod(const int x,const int y){ return 1ll*x*y%mod; }
int n,m,k,f[2005][2005],down[2005],pw[1000005];
void solve(){
	cin>>n>>m>>k,f[0][0]=down[0]=pw[0]=1;
	F(i,1,m)F(j,1,min(i,k))f[i][j]=add(f[i-1][j-1],i==1?0:(1ll*(i-1)*f[i-2][j-1]%mod));
	F(i,1,m)down[i]=1ll*down[i-1]*(k-i+1)%mod;
	F(i,1,n)pw[i]=1ll*pw[i-1]*k%mod;
	int res=0,ans=0;
	F(i,1,m)inc(res,1ll*down[i]*f[m][i]%mod);
	F(i,1,m>>1){
		const int t=m-(i<<1);
		int tot=0;
		F(j,0,min(t,k-i))inc(tot,1ll*f[t][j]*down[i+j]%mod);
		dec(res,tot);
		int flag=1;
		rep(l,m,n,i+t){
			const int val=1ll*pw[n-l]*tot%mod*(n-l+1)%mod;
			if(flag)inc(ans,val);
			else dec(ans,val);
			flag^=1;
		}
	}
	inc(ans,1ll*res*pw[n-m]%mod*(n-m+1)%mod);
	cout<<ans;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int zsy=1;
	F(____,1,zsy)solve();
}