#include <cstdio>

const int MOD = 1e4 + 7;

int pw(int a, int n, int ac) {
  if (!n) {
    return ac;
  }
  if (n & 1) {
    ac = (ac * a) % MOD;
  }
  return pw((a * a) % MOD, n / 2, ac);
}

int main() {
  int t, n, m, p, k;
  FILE *fin = fopen("matrice5.in", "r");
  fscanf(fin, "%d", &t);
  FILE *fout = fopen("matrice5.out", "w");
  while (t--) {
    fscanf(fin, "%d%d%d%d", &n, &m, &p, &k);
    fprintf(fout, "%d\n", (pw(p, n * m, 1) * pw(k, (n - 1) * (m - 1), 1)) % MOD);
  }
  fclose(fin);
  fclose(fout);
  return 0;
}