#include <fstream>
using namespace std;
ifstream in ("matrice5.in");
ofstream out ("matrice5.out");
int main()
{
    int mod=10007,t,i,j,rez,n,m,p,k,x;
    in>>t;
    for(i=1;i<=t;i++)
    {
        in>>n>>m>>p>>k;
        rez=1;
        x=(n-1)*(m-1);
        for(j=1;j<=x;j++)
        {
            rez=rez*k;
            rez%=mod;
        }
        rez%=mod;
        x=n*m;
        for(j=1;j<=x;j++)
        {
            rez=rez*p;
            rez%=mod;
        }
        out<<rez<<'\n';
    }
    return 0;
}