#include <cstdio>

#define MOD 10007

using namespace std;
int t, n, m, p, k, ans;
int power(int a, int b)
{
    int sol = 1;
    for(; b; b>>=1)
    {
        if(b&1) sol = (1LL*sol*a)%MOD;
        a = (1LL*a*a)%MOD;
    }
    return sol;
}

int main()
{
    freopen("matrice5.in", "r", stdin);
    freopen("matrice5.out", "w", stdout);
    scanf("%d", &t);
    for( ; t; --t)
    {
        scanf("%d %d %d %d", &n, &m, &p, &k);
        ans = (1LL * power(k, (n-1)*(m-1)) * power(p, n*m))%MOD;
        printf("%d\n", ans);
    }
    return 0;
}