#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("matrice5.in");
ofstream out("matrice5.out");

long long Find_close_power(int n, int &exp, int m)
{
    int pow = 1;

    while (2 * pow < exp)
    {
        n = (n * n) % m;
        pow += pow;
    }
    exp -= pow;

    return n;
}

int main()
{
    int M, N, K, P, T, m = 10007;
    in>> T;

    for (int l = 0; l < T; l++)
    {
        in>> N >> M >> P >> K;
        long long K_P = (K * P) % m, Pr_1 = 1, Pr_2 = 1;
        int exp = ((M - 1) * (N - 1));
        while (exp)
        {
            Pr_1 = (Pr_1 * Find_close_power(K_P, exp, m)) % m;
        }

        exp = N + M - 1;

        while (exp)
        {
            Pr_2 = (Pr_2 * Find_close_power(P, exp, m)) % m;
        }

        out<< (Pr_1 * Pr_2) % m << "\n";
    }
    return 0;
}