# include <cstdio>

const char *FIN = "matrice5.in", *FOU = "matrice5.out";
const int MOD = 10007;

int T, N, M, P, K;

inline int put (int N, int P) {
    int sol = 1;
    for (; P; P >>= 1) {
        if (P & 1)
            sol = (1LL * sol * N) % MOD;
        N = (1LL * N * N) % MOD;
    }
    return sol;
}

int main (void) {
    freopen (FIN, "r", stdin);
    freopen (FOU, "w", stdout);

    for (scanf ("%d", &T); T; --T) {
        scanf ("%d %d %d %d", &N, &M, &P, &K);
        printf ("%d\n", (put ((put (P * K, M - 1) * P) % MOD, N - 1) * put (P, M)) % MOD);
    }
}