#include<cstdio>

using namespace std;

int i,n,k,p,m,t,ans;

int lgput(int x,int p)
{
    int i,k=x,ans=1;
    for(i=0;(1<<i)<=p;i++)
    {
        if(p&(1<<i))
        {
            ans*=k;
            ans%=10007;
        }
        k*=k;
        k%=10007;
    }
    return ans;
}

int main()
{
    freopen("matrice5.in","r",stdin);
    freopen("matrice5.out","w",stdout);
    scanf("%d",&t);
    for(i=1;i<=t;i++)
    {
        scanf("%d%d%d%d",&n,&m,&p,&k);
        ans=lgput(k,(n-1)*(m-1))*lgput(p,n*m);
        ans%=10007;
        printf("%d\n",ans);
    }
}