#include <bits/stdc++.h>
using u64 = uint64_t;
const int P = 1e9+7;
struct mint {
	int x;
	mint(int x = 0):x(x){}
	mint operator+(mint o) {return x+o.x<P?x+o.x:x+o.x-P;}
	mint operator-(mint o) {return x-o.x<0?x-o.x+P:x-o.x;}
	mint operator*(mint o) {return u64(x)*o.x%P;}
	mint pow(int k) {
		mint a = x;
		mint b = 1;
		for(; k; k /= 2) {
			if(k & 1) 
				b = b * a;
			a = a * a;
		}
		return b;
	}
};
struct matr {
	mint a[2][2]{};
	matr operator*(matr o) {
		matr ans;
		for(int i = 0;i<2;++i)
			for(int j = 0;j<2;++j)
				for(int k = 0;k<2;++k)
					ans.a[i][k] = ans.a[i][k] + a[i][j]*o.a[j][k];
		return ans;	
	}
	matr pow(int k) {
		matr a = *this;
		matr b = {1,0,0,1};
		for(; k; k /= 2) {
			if(k & 1) 
				b = b * a;
			a = a * a;
		}
		return b;
	}
};
int i32() {
	int x;
	scanf("%d", &x);
	return x;
}
int main() {
	int T = i32();
	while(T--) {
		int n = i32();
		int k = i32();
		mint m = i32();
		matr tmp = matr{0,1,m-1,m-2}.pow(n-2)*matr{m,m,0,0};
		mint ans = tmp.a[0][0]*(m-1)+tmp.a[1][0]*(m-2);
		ans = ans * (m * m - m * 3 + 3).pow(n-1).pow(k);
		printf("%d\n", ans.x);
	}
}