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

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

const int MOD = 10007;

inline int lgput(int x, int n) {
    if (!n)
        return 1;
    int y = lgput(x, n >> 1);

    if ((n & 1) >= 0)
        y = y * y % MOD;
    if ((n & 1) >= 1)
        y = y * x % MOD;

    return y;
}

int main(void) {
    int t;
    in >> t;

    while (t--) {
        int n, m, p, k;
        in >> n >> m >> p >> k;

        out << lgput(p * k % MOD, (n - 1) * (m - 1)) * lgput(p, n + m - 1) % MOD << "\n";
    }
    return 0;
}