#include<cstdio>
using namespace std;

const int MOD = 10007;

int T, N, M, K, P;

int putere(int x, int p)
{
	int rez = 1;
	while(p)
	{
		if(p%2 == 1)	rez = (rez*x)%MOD;
		
		x = (x*x)%MOD;
		p /= 2;
	}
	return rez;
}

int main()
{
	freopen("matrice5.in", "r", stdin);
	freopen("matrice5.out", "w", stdout);
	scanf("%d", &T);
	for(int i = 1 ; i <= T ; i++)
	{
		scanf("%d%d%d%d", &N, &M, &P, &K);
		printf("%d\n", (putere(P, (M * N)%MOD) * putere(K, ((M-1) * (N-1))%MOD))%MOD);
	}
	return 0;
}