#include <fstream>
using namespace std;

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

const int mod=10007;

int pow(int a,int b)
{
	if(b==1)
		return a;
	if(b==0)
		return 1;
	if(b%2==0)
		return (pow(a,b/2)%mod)*(pow(a,b/2)%mod)%mod;
	if(b%2==1)
		return ((a%mod)*(pow(a,b/2)%mod)*(pow(a,b/2)%mod))%mod;
}
	
int main()
{
	int n,m,p,k,t,i,rez;
	in>>t;
	for(i=1;i<=t;i++)
	{
		in>>n>>m>>p>>k;
		rez=(pow(k,(m-1)*(n-1))%mod) * (pow(p,n*m) %mod) %mod;
		out<<rez<<"\n";
	}
	
	return 0;
}