#include <fstream>
using namespace std;

const int mod = 10007;

int exp(int e, int x){
	int rez = 1;
	while(x){
		if(x & 1 == 1){
			rez *= e;
			rez %= 10007; }
		e *= e;
		e %= 10007;
		x /= 2; }
	return rez; }

int main(){
	ifstream f("matrice5.in");
	ofstream g("matrice5.out");
	int t = 0;
	f >> t;
	for(int i = 0, n, m, p, k, tmp; i < t; ++i){
		f >> n >> m >> p >> k;
		tmp = n*m;
		// tmp - n - m + 1 = (n-1)*(m-1)
		g << (exp(k, tmp - n - m + 1)*exp(p, tmp))%mod << '\n'; }
	return 0; }