#include <cstdio>
#define MOD 10007

using namespace std;

inline long long PutLog(long long x, long long p)
{
    long long put=1;
    while(p)
    {
        if(p&1)
        {
            --p;
            put=(put*x)%MOD;
        }
        p/=2;
        x=(x*x)%MOD;
    }
    return put%MOD;
}

int main()
{
    long long N,M,P,T,K,sol;
    freopen ("matrice5.in","r",stdin);
    freopen ("matrice5.out","w",stdout);
    scanf("%lld", &T);
    while(T--)
    {
        scanf("%lld%lld%lld%lld", &N,&M,&P,&K);
        sol=(PutLog(K, (N-1)*(M-1)) * PutLog(P, N*M))%MOD;
        printf("%lld\n", sol);
    }
    return 0;
}