#include <bits/stdc++.h>

using namespace std;
int modulo = 10007;
int putere (int a, int b)
{
    int raspuns = 1;
    while (b)
    {
        if (b%2)
        {
            --b;
            raspuns = (raspuns*a)%modulo;
        }
        else
        {
            b/=2;
            a = (a*a)%modulo;
        }
    }
    return raspuns;
}
int main()
{
    ifstream fin ("matrice.in");
    ofstream fout ("matrice.out");
    int t, n, m, p, k;
    fin >> t;
    while (t--)
    {
        fin >> n >> m >> p >> k;
        fout << (putere(k, (n-1)*(m-1))*putere(p, n*m))%modulo << '\n';
    }
    return 0;
}