#include <fstream>

using namespace std;
int sol,modul=10007,c,n,m,p,k,t;

void putere (int a,int b);

int main ()
{
    ifstream in ("matrice5.in");
    ofstream out ("matrice5.out");
    in>>t;
    for (int z=1;z<=t;++z)
    {
        in>>n>>m>>p>>k;
        putere(k,(m-1)*(n-1));
        sol=c;
        putere(p,m*n);
        sol=(sol*c)%modul;
        out<<sol<<"\n";
    }
    in.close();
    out.close();
}

void putere (int a, int b)
{
    if (b==1)
    {
        c=a%modul;
    }else
    {
        putere(a,b/2);
        c=(c*c)%modul;
        if ((b %2)==1) c=(c*a)%modul;
    }
}