#include <bits/stdc++.h>
using namespace std;

ifstream fin("matrice5.in");
ofstream fout("matrice5.out");

const int MOD = 10007;

int pwr(int x, int n) {
    if (!n)
        return 1;
    if (n & 1)
        return x * pwr(x * x % MOD, n >> 1) % MOD;
    return pwr(x * x % MOD, n >> 1);
}

int main() {
    int t; fin >> t;
    while (t--) {
        int m, n, p, k;
        fin >> m >> n >> p >> k;
        fout << pwr(k, (m - 1) * (n - 1)) * pwr(p, m * n) % MOD << '\n';
    }

    fout.close();
    return 0;
}