#include <iostream>
using namespace std;

const int MOD = 10007;

// Fast exponentiation: computes (base^exp) % MOD
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(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;  // Number of test cases
    while(T--){
        int N, M, P, K;
        cin >> 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;
        cout << answer << "\n";
    }

    return 0;
}