#include <fstream>
#define MOD 10007

using namespace std;

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

int lgput(int base, int exp) {
  int sol;

  if (exp == 0)
    return 1;

  sol = lgput(base, exp / 2);
  sol = (sol * sol) % MOD;
  if (exp % 2 == 1)
    sol = (sol * base) % MOD;

  return sol;
}

int main() {
  int t, n, m, k, p;
  cin >> t;

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