#include<stdio.h>

#define MOD 10007

int t,n,m,p,k;

int rid_log(int val,int put)
{
	if(put==1)
		return val;
	int r=rid_log(val,put/2);
	if(put&1)
		return ((r*r%MOD)*val)%MOD;
	return r*r%MOD;
}

int main ()
{
	int i,r;

	freopen("matrice5.in","r",stdin);
	freopen("matrice5.out","w",stdout);
	scanf("%d",&t);
	for(i=1;i<=t;i++)
	{
		scanf("%d%d%d%d",&n,&m,&p,&k);
		r=rid_log(k,(n-1)*(m-1))*rid_log(p,n*m);
		r%=MOD;
		printf("%d\n",r);
	}
	return 0;
}