#include <fstream>

using namespace std;

const int MOD = 10007;

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    while (exp) {
        if (exp % 2) result = (result * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

int main() {
    ifstream fin("matrice5.in");
    ofstream fout("matrice5.out");

    int T;
    fin >> T;

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

        // Numărul total de matrici modulo 10007
        fout << power(P, N * M, MOD) << "\n";
    }

    return 0;
}