#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("matrice5.in");
ofstream fout("matrice5.out");
const int MOD = 10007;

int mod_pow(int x, int y, int mod) {
    int result = 1;
    while (y > 0) {
        if (y % 2 == 1) {
            result = (result * x) % mod;
        }
        x = (x * x) % mod;
        y /= 2;
    }
    return result;
}
int calculate_matrices(int N, int M, int P, int K) {
    int max_value = K * P;
    int combinations = mod_pow(max_value, N * M, MOD);
    int valid = combinations;
    return valid;
}

int main() {
    int T;
    fin >> T;
    while (T--) {
        int N, M, P, K;
        fin >> N >> M >> P >> K;

        int result = calculate_matrices(N, M, P, K);
        fout << result << "\n";
    }
    return 0;
}