// Mihai Gheorghe
#include <stdio.h>

int n, m, p, k;

const int mod = 10007;

int pow (int x, int p)
{
	if (p == 1)
		return x;
	
	int rez = pow (x, p / 2);
	
	rez = (rez * rez) % mod;
	if (p & 1)
		rez = (rez * x) % mod;
	return rez;
}

int main ()
{
	freopen ("matrice5.in", "r", stdin);
	freopen ("matrice5.out", "w", stdout);
	
	int t, rez;
	
	scanf ("%d", &t);
	
	while (t --)
	{
		scanf ("%d %d %d %d", &n, &m, &p, &k);
		
		rez = pow (p, n * m);
		rez = (rez * pow (k, (n - 1) * (m - 1))) % mod;
		
		printf ("%d\n", rez);
	}
	return 0;
}