#include <bits/stdc++.h>

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

const int MOD = 1e4 + 7;

int fastpower(int baza, int exp) {
    if (exp == 0) return 1;
    int r = fastpower(baza, exp / 2) % MOD;
    if (exp % 2 == 1) return r * r * baza % MOD;
    return r * r % MOD;
}
int main()
{
    int t;
    fin >> t;
    while (t--) {
        int n, m, p, k;
        fin >> n >> m >> p >> k;
        fout << fastpower(p * k, (n - 1) * (m - 1)) * fastpower(p, n + m - 1) % MOD << '\n';
    }
    return 0;
}