#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define LC k<<1
#define RC k<<1|1
#define IO cin.sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define rep(i,a,n) for (int i = a; i < n; i++)
#define repn(i,a,n) for (int i = a; i <= n; i++)
#define per(i,a,n) for (int i = (n) - 1; i >= a; i--)
#define pern(i,a,n) for (int i = n; i >= a; i--)

typedef long long LL;
typedef long double LD;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<int, LL> PIL;
typedef pair<LL, int> PLI;
typedef pair<double, double> PDD;
typedef pair<ull, ull> PUU;
typedef pair<LL, LL> PLL;

const int N = 110000;
const int M = 1100000;
const int mod = 1e9+7;
const int inf = (int)1e9;
const LL INF = 1e18;
const double eps = 1e-9;

mt19937_64 Rand((unsigned long long)new char);
#define rand Rand

int T;
LL n, k, m;
LL pow_mod(LL a, LL e) {
	LL res = 1;
	for (; e; a = a * a % mod, e >>= 1) if (e & 1) res = res * a % mod;
	return res;
}
const int MAXN = 2;
struct Matrix {
	int n, m;
	LL a[MAXN][MAXN];
	void clear() {
		n = m = 0;
		memset(a, 0, sizeof(a));
	}
	void unit() {
		memset(a, 0, sizeof(a));
		rep(i, 0, n) a[i][i] = 1;
	}
	LL pow_mod(LL a, LL e) {
		LL res = 1;
		for (; e; a = a * a % mod, e >>= 1) if (e & 1) res = res * a % mod;
		return res;
	}
	Matrix split(int x1, int y1, int x2, int y2) {
		Matrix res;
		res.clear(); res.n = x2 - x1 + 1, res.m = y2 - y1 + 1;
		repn(i, x1, x2) repn(j, y1, y2) res.a[i - x1][j - y1] = a[i][j];
		return res;
	}
	Matrix operator * (const Matrix &b) const {
		Matrix tmp;
		tmp.clear();
		tmp.n = n, tmp.m = b.m;
		rep(i, 0, n) rep(j, 0, b.m) rep(k, 0, m) 
		    tmp.a[i][j] = (tmp.a[i][j] + a[i][k] * b.a[k][j]) % mod;
		return tmp;
    }
	LL det_mod() {
		assert(n == m);
		rep(i, 0, n) rep(j, 0, m) a[i][j] = (a[i][j] + mod) % mod;
		LL res = 1;
		rep(i, 0, n) {
			if (!a[i][i]) {
				rep(j, i, n) {
					if (a[j][i]) {
						rep(k, i, n) swap(a[j][k], a[i][k]);
						break;
					}
				}
				res = mod - res;
			}
			LL inv = pow_mod(a[i][i], mod - 2);
			rep(j, 0, n) {
				if (j != i) {
					LL coef = inv * a[j][i] % mod;
					rep(k, i, n) a[j][k] = (a[j][k] - coef * a[i][k] % mod + mod) % mod;
				}
			}
		}
		rep(i, 0, n) res = res * a[i][i] % mod;
		return res;
	}
}A;
Matrix pow_mod(Matrix a, LL e) {	
	Matrix res = a;
	res.unit();
	for (; e; a = a * a, e >>= 1) if (e & 1) res = res * a;
	return res;
}
int main() {
	IO;
	cin >> T;
	while (T--) {
		cin >> n >> k >> m;
		if (m < 2) {
			cout << "0\n";
			continue;
		}
		A.clear();
		A.n = A.m = 2, A.a[0][0] = 0, A.a[0][1] = m - 1, A.a[1][0] = 1, A.a[1][1] = m - 2;
		A = pow_mod(A, k - 1);
		LL ans = m * A.a[0][1] % mod;
		LL p = m - 1 + (m - 2) * (m - 2);
		ans = ans * pow_mod(p % mod, (n - 1) * k) % mod;
		cout << ans << "\n";
	}
	return 0;
}