#include <cstdio>

#define NMax 1005
#define MMax 1000
#define PMax 1000
#define KMax 1000
#define Mod 10007

using namespace std;

int KM[NMax][NMax], PM[NMax][NMax];

void BuildPM ()
{
    for (int P=1; P<=PMax; ++P)
    {
        PM[P][0]=1;
        for (int M=1; M<=MMax; ++M)
        {
            PM[P][M]=P*PM[P][M-1];
            PM[P][M]%=Mod;
        }
    }
}

void BuildKM ()
{
    for (int K=1; K<=KMax; ++K)
    {
        KM[K][1]=1;
        for (int M=2; M<=MMax; ++M)
        {
            KM[K][M]=K*KM[K][M-1];
            KM[K][M]%=Mod;
        }
    }
}

int Pow (int X, int P)
{
    int S=1;
    while (P>0)
    {
        if (P%2==0)
        {
            X*=X;
            X%=Mod;
            P/=2;
        }
        S*=X;
        S%=Mod;
        --P;
    }
    return S;
}

int Query (int N, int M, int P, int K)
{
    int Line=(KM[K][M]*PM[P][M])%Mod;
    return (Pow (Line, N-1)*PM[P][M])%Mod;
}


int main()
{
    freopen ("matrice5.in", "r", stdin);
    freopen ("matrice5.out", "w", stdout);
    BuildPM ();
    BuildKM ();
    int T;
    scanf ("%d", &T);
    for (; T>0; --T)
    {
        int N, M, P, K;
        scanf ("%d %d %d %d", &N, &M, &P, &K);
        printf ("%d\n", Query (N, M, P, K));
    }
    return 0;
}