#include <fstream>	
#include <vector>
#include <bitset>
#include <string.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <time.h>
#include <stdlib.h>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <deque>


using namespace std;

ifstream fin("matrice5.in");
ofstream fout("matrice5.out";



const int MAXN = 100005;
const int MOD = 10007;
const int oo = 0x3f3f3f3f;

const inline int min(const int& a, const int& b) 
{
	if (a > b) return b;
	return a;
}

const inline int max(const int& a, const int& b) 
{ 
	if (a < b) return b;
	return a;
}

const inline void Get_min(int& a, const int b) 
{
	if (a > b) a = b; 
}

const inline void Get_max(int& a, const int b) 
{
	if (a < b) a = b;
}

inline int lgPow(int N, int P) 
{
	int Ans = 1;
	for (; P; P >>= 1)
	{
		if (P & 1)
			Ans = (1LL * Ans * N) % MOD;
	N = (1LL * N * N) % MOD;
	}
	return Ans;

}

inline int Solve(int N, int M, int P, int K) {

	return (1LL * lgPow(K * P, (N - 1) * (M - 1)) * lgPow(P, (N + M - 1))) % MOD;

}



int main()
{

	int T, N, M, P, K;

	fin >> T;

	while (T--)
	{
		fin >> N >> M >> P >> K;
		fout << Solve(N, M, P, K) << '\n';
	}
	return 0;

}