#include <iostream>

using namespace std;

typedef long long i64;

const i64 MOD = 10007;

i64 n, m, k, p;

inline i64 plog(i64 BAZA, const i64 EXPONENT) {
    i64 R = 1;
    BAZA %= MOD;
    for(i64 i = 1; i <= EXPONENT; i <<= 1) {
        if(i & EXPONENT) R = (R * BAZA) % MOD;
        BAZA = (BAZA * BAZA) % MOD;
    }
    return R %= MOD;
}

int main()
{
    freopen("matrice5.in", "r", stdin);
    freopen("matrice5.out", "w", stdout);
    int TESTS;
    scanf("%hd", &TESTS);
    while(TESTS--)
        scanf("%lld%lld%lld%lld", &n, &m, &p, &k),
        printf("%lld\n",
               plog(k, (n - 1) * (m - 1)) *
               plog(p, n * m) % MOD);
    return 0;
}