#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
long long fact[200001],invfact[200001];
int main(){
	int n,k;
	long long m;
	cin>>n>>m>>k;
	fact[0]=1;
	for(int i=1;i<=k;i++)
		fact[i]=fact[i-1]*i%mod;
	for(int i=0;i<=k;i++){
		long long a=fact[i];
		long long mm=mod-2;
		long long b=1;
		while(mm){
			if(mm&1)
				(b*=a)%=mod;
			(a*=a)%=mod;
			mm>>=1;
		}
		invfact[i]=b;
	}
	int ans=0;
	for(long long i=1;i<=k;i++){
		long long tmp=0;
		if(n==1){
			long long a=i-1;
			long long x=i;
			long long mm=m-1;
			long long b=1;
			while(mm){
				if(mm&1)
					(b*=a)%=mod;
				(a*=a)%=mod;
				mm>>=1;
			}
			tmp=b*x%mod;
		}
		if(n==2){
			long long a=(i*i-3*i+3)%mod;
			long long x=(i*i-i)%mod;
			long long mm=m-1;
			long long b=1;
			while(mm){
				if(mm&1)
					(b*=a)%=mod;
				(a*=a)%=mod;
				mm>>=1;
			}
			tmp=b*x%mod;
		}
		if(n==3){
			long long a00=(i*i*i-i*i*6+i*14-13)%mod;
			long long a01=(i*i*i-i*i*6+i*13-10)%mod;
			long long a10=(i*i-i*4+5)%mod;
			long long a11=(i*i-i*3+3)%mod;
			long long x=(i*i*i-i*i*3+i*2)%mod;
			long long y=(i*i-i)%mod;
			long long mm=m-1;
			long long b00=1,b01=0,b10=0,b11=1;
			while(mm){
				if(mm&1){
					long long bb00=(b00*a00+b01*a10)%mod;
					long long bb01=(b00*a01+b01*a11)%mod;
					long long bb10=(b10*a00+b11*a10)%mod;
					long long bb11=(b10*a01+b11*a11)%mod;
					b00=bb00;
					b01=bb01;
					b10=bb10;
					b11=bb11;
				}
				long long aa00=(a00*a00+a01*a10)%mod;
				long long aa01=(a00*a01+a01*a11)%mod;
				long long aa10=(a10*a00+a11*a10)%mod;
				long long aa11=(a10*a01+a11*a11)%mod;
				a00=aa00;
				a01=aa01;
				a10=aa10;
				a11=aa11;
				mm>>=1;
			}
			tmp=(b00*x+b01*y+b10*x+b11*y)%mod;
		}
		(tmp*=fact[k]*invfact[i]%mod*invfact[k-i]%mod)%=mod;
		if((k-i)%2==1)
			tmp=(-tmp+mod)%mod;
		(ans+=tmp)%=mod;
	}
	cout<<ans<<endl;
}