#include <iostream>
using namespace std;
const long long modf = 1e9 + 7;
long long T, n, k, u;
long long fjz[3][3], xl[3];

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

void jzqc(long long y) {
	long long tmpjz[3][3], njz[3][3];
	tmpjz[1][1] = u - 2, tmpjz[2][1] = u - 1;
	tmpjz[1][2] = 1, tmpjz[2][2] = 0;
	fjz[1][1] = 1;
	fjz[2][2] = 1;
	while (y) {
		if (y & 1) {
			for (int i = 1; i <= 2; ++i) {
				for (int j = 1; j <= 2; ++j) {
					njz[i][j] = fjz[i][j];
				}
			}
			fjz[1][1] = njz[1][1] * tmpjz[1][1] + njz[1][2] * tmpjz[2][1];
			fjz[1][2] = njz[1][1] * tmpjz[1][2] + njz[1][2] * tmpjz[2][2];
			fjz[2][1] = njz[2][1] * tmpjz[1][1] + njz[2][2] * tmpjz[2][1];
			fjz[2][2] = njz[2][1] * tmpjz[1][2] + njz[2][2] * tmpjz[2][2];
			for (int i = 1; i <= 2; ++i) {
				for (int j = 1; j <= 2; ++j) {
					fjz[i][j] %= modf;
				}
			}
		}
		for (int i = 1; i <= 2; ++i) {
			for (int j = 1; j <= 2; ++j) {
				njz[i][j] = tmpjz[i][j];
			}
		}
		tmpjz[1][1] = njz[1][1] * njz[1][1] + njz[1][2] * njz[2][1];
		tmpjz[1][2] = njz[1][1] * njz[1][2] + njz[1][2] * njz[2][2];
		tmpjz[2][1] = njz[2][1] * njz[1][1] + njz[2][2] * njz[2][1];
		tmpjz[2][2] = njz[2][1] * njz[1][2] + njz[2][2] * njz[2][2];
		for (int i = 1; i <= 2; ++i) {
			for (int j = 1; j <= 2; ++j) {
				tmpjz[i][j] %= modf;
			}
		}
		y >>= 1;
	}
}

void solve() {
	cin >> n >> k >> u;
	if (u <= 2) {
		cout << 0;
		return;
	}
	//\xd6\xdcΧ
	long long d = ((u - 2) * (u - 2) % modf + u - 1) % modf;
	long long v = k * (n - 1) % modf;
	long long dy = qc(d, v);

	//\xbb\xb7
	xl[1] = u * (u - 1) % modf, xl[2] = u;

	jzqc(k - 1);
	long long c = fjz[1][2] * xl[1] % modf + fjz[2][2] * xl[2] % modf;
	c %= modf;
	if (k == 3)
		c = 6;
	long long ans = c * dy % modf;
	cout << ans << '\n';
}

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> T;
	while (T--) {
		solve();
	}

	return 0;
}