#include <fstream>

using namespace std;

ifstream in("matrice5.in");
ofstream out("matrice5.out");


int teste;
int n, m, k, p, ANS;

const int MOD = 10007;

int exp(int a, int pow) {
    if (!pow) {
        return 1;
    }

    int b = exp(a, pow / 2);
    
    if (pow % 2 == 1) {
        return (b * b) % MOD * a % MOD;
    } else {
        return b * b % MOD;
    }
}

int main() {
    
    in >> teste;

    while (teste--) {
        in >> n >> m >> p >> k;
        
        ANS = exp(k, (n - 1) * (m - 1));
        ANS = (ANS * exp(p, n * m)) % MOD;

        out << ANS << "\n";
    }
  
    return 0;
}