#include <stdio.h>
#define MOD 10007
#define MAXN 1000
#define MAXK 1000

inline int ptr(int a, int b){
  int rez = 1;
  while(b > 0){
    if(b & 1){
      rez *= a;
      rez %= MOD;
    }
    b /= 2;
    a *= a;
    a %= MOD;
  }
  return rez;
}

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