#include <iostream>
#include <bits/stdc++.h>
#define INFILE "matrice5.in"
#define OUTFILE "matrice5.out"

using namespace std;

ifstream in(INFILE);
ofstream out(OUTFILE);

const int MOD=10007;

int putere(int baza,int exp){
    int ret=1;
    while(exp>0){
        if(exp%2==1){
            exp--;
            ret*=baza;
            ret=ret%MOD;
        }
        exp/=2;
        baza=(baza*baza)%MOD;
    }
    return ret;
}

int main()
{
    int T;
    in>>T;
    for(int i=1;i<=T;i++){
        int N,M,P,K;
        in>>N>>M>>P>>K;
        out<<(putere(K,(N-1)*(M-1))*putere(P,N*M))%MOD<<"\n";
    }
    return 0;
}