#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

const int MOD = 10007;

// Function to calculate modular exponentiation
int mod_pow(int base, int exp, int mod) {
    int result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

// Function to calculate factorial modulo MOD
int factorial_mod(int n, int mod) {
    int result = 1;
    for (int i = 2; i <= n; ++i) {
        result = (result * i) % mod;
    }
    return result;
}

// Function to calculate the number of valid matrices
int countValidMatrices(int N, int M, int P, int K) {
    // Calculate the number of valid entries per cell
    int valid_entries = P;
    while (valid_entries % K != 0) {
        valid_entries += P;
    }
    valid_entries /= K;

    // Calculate the number of ways to fill an N x M matrix
    int total_cells = N * M;
    int result = mod_pow(valid_entries, total_cells, MOD);

    return result;
}

int main() {
    // Open input and output files
    freopen("matrice5.in", "r", stdin);
    freopen("matrice5.out", "w", stdout);

    int T;
    cin >> T;

    while (T--) {
        int N, M, P, K;
        cin >> N >> M >> P >> K;

        int result = countValidMatrices(N, M, P, K);
        cout << result << endl;
    }

    return 0;
}