#include <fstream>

using namespace std;

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

const int MOD = 10007;

int lgput( int a, int b ){
  int p = 1;
  while( b > 0 ){
    if( b % 2 == 1 )
      p = (p * a) % MOD;
    a = (a * a) % MOD;
    b /= 2;
  }
  return p;
}

int main() {
  int q, i, n, m, p, k;
  fin >> q;
  for( i = 1; i <= q; ++i ) {
    fin >> n >> m >> p >> k;
    fout << lgput(k, (n - 1) * (m - 1)) * lgput(p, n * m) % MOD << "\n";
  }
  return 0;
}