#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>

const int kModulo = 10007;

inline int Power(int base, int power) {
	int res = 1;
	while (power > 0) {
		if (power & 1)
			res = res * base % kModulo;

		power >>= 1;
		base = base * base % kModulo;
	}

	return res;
}

int main() {
	std::ifstream inputFile("matrice5.in");
	std::ofstream outputFile("matrice5.out");

	int testCount;
	inputFile >> testCount;

	while (testCount--) {
		int n, m, p, k;
		inputFile >> n >> m >> p >> k;

		int res = Power(p*k % kModulo, (n - 1)*(m - 1));
		res = res * Power(p, n + m - 1);
		res %= kModulo;

		outputFile << res << '\n';
	}

	inputFile.close();
	outputFile.close();

	return 0;
}

//Trust me. I'm the Doctor!