#include <fstream>

using namespace std;

const char InFile[]="matrice5.in";
const char OutFile[]="matrice5.out";
const int MOD=10007;

ifstream fin(InFile);
ofstream fout(OutFile);

int T,N,M,P,K;

inline int mypow(int A, int B)
{
	int sol=1;
	for(;B;B>>=1)
	{
		if(B&1)
		{
			sol*=A;
			sol%=MOD;
		}
		A*=A;
		A%=MOD;
	}
	return sol;
}

int main()
{
	fin>>T;
	for(register int i=0;i<T;++i)
	{
		fin>>N>>M>>P>>K;
		int L=(mypow((P*K)%MOD,M-1)*P)%MOD;
		fout<<(mypow(L,N-1)*mypow(P,M))%MOD<<"\n";
	}
	fin.close();
	fout.close();
	return 0;
}