#include <bits/stdc++.h>
#define MAX 131072
#define MOD 10007

using namespace std;

int T, N, M, P, K;

int lgput(int x, int p){
    int n = 1;
    for(int i = 0; i < 32; i++){
        if(p & (1 << i))
            n = (1LL * n * x) % MOD;
        x = (1LL * x * x) % MOD;
    }
    return n;
}

int main(){

    freopen("matrice5.in", "r", stdin);
    freopen("matrice5.out", "w", stdout);

    scanf("%d", &T);
    for(; T; --T){
        scanf("%d%d%d%d", &N, &M, &P, &K);
        if(M > N) swap(N, M);
        printf("%d\n", (1LL * lgput(P, N + M - 1)) * lgput(K * P, (N - 1) * (M - 1)) % MOD);
    }

    return 0;
}