#include <bits/stdc++.h>
using namespace std;

const int MOD = 10007;

// Fast exponentiation: computes (base^exp) % MOD efficiently.
int modExp(int base, int exp) {
    long long result = 1;
    long long b = base % MOD;
    while(exp > 0) {
        if(exp & 1)  // If the current exponent bit is 1
            result = (result * b) % MOD;
        b = (b * b) % MOD;
        exp >>= 1;   // Divide the exponent by 2
    }
    return (int) result;
}

int main(){
    // Open the input and output files.
    // Make sure that "matrice5.in" is in the same folder as your executable.
    ifstream in("matrice5.in");
    ofstream out("matrice5.out");

    int T;
    in >> T;  // Number of test cases
    while(T--){
        int N, M, P, K;
        in >> N >> M >> P >> K;

        // Compute P^(N*M) mod MOD.
        int exp1 = N * M;
        int part1 = modExp(P, exp1);

        // Compute K^((N-1)*(M-1)) mod MOD.
        int exp2 = (N - 1) * (M - 1);
        int part2 = modExp(K, exp2);

        // Final answer = part1 * part2 mod MOD.
        int answer = ( (long long) part1 * part2 ) % MOD;
        out << answer << "\n";
    }

    // Close the files.
    in.close();
    out.close();

    return 0;
}