#include<cstdio>

const int MOD = 10007;

int n, m, p, k;

int formula() {
    int prod = 1;
    for (int i = 1; i <= (n - 1) * (m - 1); ++i) {
        prod *= k;
        prod %= MOD;
    }

    for (int i = 1; i <= (n * m); ++i) {
        prod *= p;
        prod %= MOD;
    }

    return prod;
}

void rez() {
    int t;
    scanf("%d", &t);

    for (int i = 1; i <= t; ++i) {
        scanf("%d%d%d%d", &n, &m, &p, &k);

        printf("%d\n", formula());
    }
}

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

    rez();

    return 0;
}