#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int MOD = 1e9 + 7;

inline void Inc(int &x, int y) {
	x += y; if (x >= MOD) x -= MOD;
}
inline void Dec(int &x, int y) {
	x -= y; if (x < 0) x += MOD;
}
inline int Mul(int x, int y) {
	return 1LL * x * y % MOD;
}
inline int Ksm(int x, int y) {
	int ret = 1;
	for (; y; y >>= 1) {
		if (y & 1) ret = Mul(ret, x);
		x = Mul(x, x);
	}
	return ret;
}
inline int Inv(int x) {
	return Ksm(x, MOD - 2);
}

void solve() {
	int n, k, c;
	scanf("%d %d %d", &n, &k, &c);
	if (c <= 1) {
		puts("0");
		return;
	}
	if ((k & 1) && c == 2) {
		puts("0");
		return;
	}
	int ans = 1;
	if (k & 1) {
		Inc(ans, Ksm(c - 1, k));
	} else {
		Dec(ans, Ksm(c - 1, k));
	}
	ans = Mul(ans, Inv(c));
	Dec(ans, 1);
	if (!(k & 1)) {
		ans = (MOD - ans) % MOD;
	}
	ans = Mul(ans, c);
	cerr << ans << endl;
	int d = 1;
	if (c >= 3) {
		Inc(d, Mul(2, c - 2));
	}
	if (c >= 4) {
		Inc(d, Mul(c - 2, c - 3));
	}
	ans = Mul(ans, Ksm(d, 1LL * k * (n - 1) % (MOD - 1)));
	printf("%d\n", ans);
}

int main() {
	int T; scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}