#include <bits/stdc++.h>
#define mod 1'000'000'007
#define ll long long
using namespace std;

int v[100100];

struct mat {

	ll M[2][2];

	mat operator*(mat a){
		
		mat ret;
		
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++){
				ret.M[i][j] = 0;
				for(int k=0;k<2;k++)
					ret.M[i][j] += M[i][k] * a.M[k][j];
				ret.M[i][j] %= mod;
			}
			
		return ret;
		
	}
	
};

mat id;

mat exp(mat A,ll k){
	if(k == 0) return id;
	mat aux = exp(A,k/2);
	aux = aux * aux;
	if(k%2 == 1)
		aux = aux * A;
	return aux;
}

ll exp(ll a,ll b){
	if(b == 0) return 1;
	ll k = exp(a,b/2);
	k = (k*k) % mod;
	if(b%2 == 1)
		k = (k*a) % mod;
	return k;
}
		

main(){

	int nt;
	scanf("%d",&nt);
	
	while(nt--){
	
		ll n,k,lam;
		scanf("%lld%lld%lld",&n,&k,&lam);
		
		id.M[0][0] = id.M[1][1] = 1;
		
		mat A;
		
		A.M[0][0] = 0;
		A.M[1][0] = 1;
		A.M[0][1] = lam-1;
		A.M[1][1] = lam-2;
		
		A = exp(A,k-1);
		
		ll D = A.M[0][1];
		
		D *= lam;
		D %= mod;
		
		ll line = ( (lam-1)*(lam-1) - (lam-2)) % mod;
		ll qtd_lines = ( k * (n-1)) % (mod-1);
		
		ll borda = exp(line,qtd_lines);
		
		ll ans = (D * borda) % mod;
		
		printf("%lld\n",ans);
		
	}

}