#include <cstdio>

FILE* in=fopen("matrice5.in","r");
FILE* out=fopen("matrice5.out","w");

const int R=10007;

long long pow(int x, int p)
{
    long long act=x,rez=1;

    while(p)
    {
        if(p&1)
        {
            rez*=act;
            rez%=R;
        }
        p/=2;
        act=act*act;
        act%=R;
    }

    return rez;
}


int main()
{
    int t;

    int n,m,p,k;

    fscanf(in,"%d",&t);

    for(int i=1; i<=t; i++)
    {
        fscanf(in,"%d%d%d%d",&n,&m,&p,&k);

        long long   act=pow(p,n*m);
        long long   act2=pow(k,(n-1)*(m-1));

        fprintf(out,"%lld\n",(act*act2)%R);
    }

    return 0;
}