#include <cstdio>

using namespace std;

const int Mod = 10007;

int q, n, m, p, k;

int power(int a, int b)
{
    if(!b) return 1;
    if(b&1) return a * power(a*a%Mod, b/2) % Mod;
    return power(a*a%Mod, b/2);
}

int main()
{
    freopen("matrice5.in", "r", stdin);
    freopen("matrice5.out", "w", stdout);

    scanf("%d", &q);
    while(q--)
    {
        scanf("%d%d%d%d", &n, &m, &p, &k);
        printf("%d\n", power(k, n*m-n-m+1) * power(p, n*m) % Mod);
    }

    return 0;
}