#include <cstdio>

using namespace std;

int main()
{
    freopen("matrice5.in","r",stdin);
    freopen("matrice5.out","w",stdout);
    long long n,m,p,k,t,rez,aux,aux2;

    scanf("%I64d",&t);

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

        //p*k ^ (n-1)(m-1)
        rez=1;
		aux2 = 1;
		for(int j=1; j<=n-1; j++)
		{
			aux2 = aux2 * p*k;
			aux2 = aux2 % 10007;
		}
        for(int j=1; j<=m-1; j++)
        {
            rez = rez * aux2;
            rez = rez % 10007;
        }

        // * p^(n+m-1)
		aux = (n+m-1);
        for(int j=1; j<=aux; j++)
        {
            rez = rez * p;
            rez = rez % 10007;
        }

        printf("%I64d\n",rez);
    }
    return 0;
}