#include <fstream>
using namespace std;

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

int exp(int b_, int e)
{
	int b = b_, rez = 1;
	while (e)
	{
		if (e&1)
			rez = rez * b % 10007;
		b = b * b % 10007;
		e >>= 1;
	}
	return rez;
}

int main()
{
	int t, i;
	int n, m, p, k;
	fin >> t;
	for (i = 1; i<=t; i++)
	{
		fin >> n >> m >> p >> k;
		fout << exp(exp(k*p%10007, m-1)*p%10007, n-1)*exp(p, m)%10007 << '\n';
	}
	return 0;
}