#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MOD=1e9+7;
ll n,k,c; 
ll ksm(ll a,int b){ll r=1;while(b){if(b&1)r=r*a%MOD;a=a*a%MOD,b>>=1;}return r;} 
struct matrix{
	ll a[2][2];
	matrix(){memset(a,0,sizeof(a));}
};
matrix operator *(matrix A,matrix B){
	matrix C;
	for(int i:{0,1}) for(int j:{0,1}) for(int k:{0,1}){
		C.a[i][j]+=A.a[i][k]*B.a[k][j];
		C.a[i][j]%=MOD;
	}
	return C;
}
void solve(){
	cin>>k>>n>>c;
	matrix A,B;
	A.a[0][0]=1;
	B.a[0][0]=0;B.a[0][1]=1;
	B.a[1][0]=c-1;B.a[1][1]=c-2;
	for(int i=0;i<=62;i++){
		if((n-1)>>i&1) A=A*B;
		B=B*B;
	} 
	cout<<c*(c-1)%MOD*A.a[0][1]%MOD*ksm(((c-1)*(c-1)-(c-2))%MOD,n*(k-1))%MOD<<endl;
}
int main(){
	ios::sync_with_stdio(false);
	int _;cin>>_;
	while(_--) solve();
}