#include <fstream>

using namespace std;

long long n,m,k,p,t,i;
int a=10007;
ifstream fi("matrice5.in");
ofstream fo("matrice5.out");

long long exponentiere(long long x, long long p)
{
    if(p==1)
        return x%a;
    if(p%2==0)
        return exponentiere(x*x%a, p/2);
    else
        return exponentiere(x*x%a, p/2)*x%a;
}

int main()
{
    fi>>t;
    for(i=1;i<=t;i++)
    {
        fi>>n>>m>>p>>k;
        fo<<(exponentiere(k,(n-1)*(m-1))*exponentiere(p,n*m))%a<<'\n';
    }
}