#include <cstdio>
#define mod 10007

int t, n, m, p, k, sol;

int pow(int n, int p)
{
	int r=1, i;
	for (i=1; i<=p; i<<=1)
	{
		if (i&p) r=(r*n)%mod;
		n=n*n%mod;
	}
	return r;
}

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