#include <iostream>
using namespace std;
const int mo = 1e9 + 7;
int T;
long long n, k, u;
long long Ln, ans;

struct Matrix {
	int numH, numL;
	long long a[5][5] = {0};

	Matrix operator*(Matrix mt) {
		Matrix res;
		res.numL = numL;
		res.numH = mt.numH;
		for (int i = 1; i <= res.numL; ++i) {
			for (int j = 1; j <= res.numH; ++j) {
				for (int k = 1; k <= numH; ++k) {
					res.a[i][j] = (res.a[i][j] + a[i][k] * mt.a[k][j]) % mo;
				}
			}
		}
		return res;
	}

};

Matrix Omt, Emt;

long long qc(long long x, long long y) {
	long long res = 1;
	while (y) {
		if (y & 1)
			res = res * x % mo;
		x = x * x % mo;
		y >>= 1;
	}
	return res;
}

Matrix mtqc(Matrix a, long long x) {
	Matrix res = Emt;
	while (x) {
		if (x & 1)
			res = res * a;
		a = a * a;
		x >>= 1;
	}
	return res;
}

void solve() {
	cin >> n >> k >> u;
	long long d = ((u - 2) * (u - 2) - 1 + u) % mo;		//һ\xb8\xf6\xc6\xe6\xc3\xee\xb5ij\xa3\xca\xfd
	Ln = qc(d, k * (n - 1));

	Omt.numH = Omt.numL = 2;
	Omt.a[1][1] = u - 2, Omt.a[1][2] = u - 1;
	Omt.a[2][1] = 1, Omt.a[2][2] = 0;

	Matrix fmt = mtqc(Omt, k - 2);

	long long c = u * (u - 1) % mo * fmt.a[1][1] % mo;
	ans = c * Ln % mo;
	cout << ans << '\n';
}

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	Emt.numH = Emt.numL = 2;
	Emt.a[1][1] = Emt.a[2][2] = 1;		//2*2\xb5\xa5λ\xbe\xd8\xd5\xf3

	cin >> T;

	while (T--) {
		solve();
	}

	return 0;
}