#include <cstdio>
const int mod=10007;

using namespace std;

int power(int n, int p)
{
    int x, power=1;
    x=n;
    for(int i=0;(1<<i)<=p;i++)
    {
        if(((1<<i)&p)>0)
            power=(power*x)%mod;
        x=(x*x)%mod;
    }
    return power;
}

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