#include <fstream>

using namespace std;

const int MOD = 10007;

int Q, N, M, P, K;
int power(int x, int y)
{
	if (y == 0) return 1;
	if (y % 2 == 0) 
		return power(x * x % MOD, y >> 1);
	return x * power(x * x % MOD, y >> 1) % MOD;
}

int main()
{
	ifstream fin("matrice5.in");
	ofstream fout("matrice5.out");
	
	fin >> Q;
	while (Q--)
	{
		fin >> N >> M >> P >> K;
		fout << power(K, (N - 1) * (M - 1)) * power(P, N * M) % MOD << '\n';
	}

}