#include <fstream>
#include <iostream>

using namespace std;

#define mod 10007

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

long long exp(long n,long p,long m)
{
    long long a=n,result=1;
    for (int i = 0; (1<<i) <= p;i++)
    {
        if ( ((1<<i) & p) > 0) result= (result * a) % m;
        a=(a * a) % m;
    }
    return result;
}

int main()
{
    long N;
    long n,m,p,k;
    long long r;
    f>>N;
    for(int i=1;i<=N;i++)
    {
        f>>n>>m>>p>>k;
        r=exp(p,m*n,mod)*exp(k,(m-1)*(n-1),mod)%mod;
        g<<r<<'\n';
    }
    return 0;
}