#include <cstdio>
#include <algorithm>

using namespace std;

#define inFile "matrice5.in"
#define outFile "matrice5.out"
#define MOD 10007

FILE *in = fopen(inFile, "r");
FILE *out = fopen(outFile, "w");

int getExp(int Base, int Exp);

int main() {
    int testCase, N, M, P, K, Ans;
    
    fscanf(in, "%d", &testCase);
    while(testCase--) {
        fscanf(in, "%d %d %d %d", &N, &M, &P, &K);
        Ans = (getExp(K, (N-1)*(M-1)) * getExp(P, N*M)) % MOD;
        fprintf(out, "%d\n", Ans);
    }
    
    fclose(in);
    fclose(out);
    
    return 0;
}

int getExp(int Base, int Exp) {
    int i, Pow = Base, Ans = 1;
    for(i = 0; (1<<i) <= Exp; i++) {
        if(Exp & (1<<i)) {
            Ans = (Ans * Pow) % MOD;
        }
        Pow = (Pow * Pow) % MOD;
    }
    return Ans;
}