#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

#ifdef LOCAL
#define fin cin
#define fout cout
#else
ifstream fin("matrice5.in");
ofstream fout("matrice5.out");
#endif

const int MOD = 10007;

int exp(int b, int p) {
	if (p == 0) return 1;
	int tmp = exp(b, p / 2);
	if (p % 2 == 0) return tmp * tmp % MOD;
	else return ((tmp * tmp) % MOD * b) % MOD;
}

int main() {
	int t, n, m, p, k;
	fin >> t;
	for (int i=1; i<=t; i++) {
		fin >> n >> m >> p >> k;
		// rasp = p ^ (n * m) * k ^ ((n - 1) * (m - 1))
		fout << exp(p, n * m) * exp(k, (n - 1) * (m - 1)) % MOD << "\n";
	}
}