#include<fstream>
using namespace std;
#define MOD 10007
long long z=MOD;
long long w;
inline int put(int N,int K)
{//printf("%d %d\n",N,K);
    int rez=1;
    int M=N;
 for(int i=0;1LL*(1<<i)<=K;++i)
    {
        if((1<<i)&K)
        {//printf("%d\n",i);
            rez*=M;
            rez%=MOD;
        }
        M*=M;
        M%=MOD;

    }
    return rez;
}
long long N;
int x,y,p,e;
int main()
{
ifstream fin("matrice5.in");
ofstream fout("matrice5.out");

    fin>>N;
   // printf("%d",put(2,7));
    for(int i=1;i<=N;++i)
    {
        fin>>x>>y>>p>>e;
        if(x!=1&&y!=1)
        fout<<((put(p*e,(x-1)*(y-1)))*put(p,x*y-(x-1)*(y-1)))%MOD<<"\n";
        else if(x==1)
        {
            fout<<((put(x-1,p*e)*p)%MOD)<<"\n";
        }
        else
        {
            fout<<((put(y-1,p*e)*p)%MOD)<<"\n";
        }
    }
}