#include <fstream>

using namespace std;

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

const int MOD = 10007;

int t, n, m, p, k;

int lgput(int n, int p) {
  int ans = 1, x = n;
  for(int i = 0; (1 << i) <= p; i++) {
    if((1 << i) & p)
      ans = ans * x % MOD;
    x = x * x % MOD;
  }
  return ans;
}

int main() {
  cin >> t;
  for(; t; t--) {
    cin >> n >> m >> p >> k;
    cout << lgput(p, n * m) * lgput(k, (n - 1) * (m - 1)) % MOD << "\n";
  }
  return 0;
}