#include <fstream>

using namespace std;

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

int t;
int r = 10007;

int exp(int a, int b)
{
    if(b == 0){
        return 1;
    }
    if(b % 2 == 0){
        return (exp(a, b / 2) * exp(a, b / 2)) % r;
    }
    if(b % 2 == 1){
        return (exp(a, b - 1) * a) % r;
    }
}

int main()
{
    fin >> t;
    for(int i = 0; i < t; ++i){
        int n, m, p, k;
        fin >> n >> m >> p >> k;
        fout << (exp(k, (n - 1) * (m - 1)) * exp(p, n * m)) % r << '\n';
    }
    return 0;
}