#include <bits/stdc++.h>

using namespace std;

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

const int mod = 10007;

int Pow(int x, int n) {
    int ans = 1;
    while(n) {
        if(n & 1)
            ans = ans * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return ans;
}

void test_case() {
    int N, M, P, K;
    fin >> N >> M >> P >> K;
    fout << Pow(K, (N - 1) * (M - 1))  * Pow(P, N * M) % mod << '\n';
}

int main() {
    int T;
    fin >> T;
    for(int tc = 0; tc < T; ++tc)
        test_case();
}