#include <stdio.h>
#include <stdlib.h>

int main() {
    FILE *fin, *fout;
    fin = fopen ( "matrice5.in", "r" );
    fout = fopen ( "matrice5.out", "w" );
    int t, n, m, p, k, x, j, cnt, y;
    fscanf ( fin, "%d", &t );
    int i;
    for ( i = 0; i < t; i ++ ) {
      fscanf ( fin, "%d%d%d%d", &n, &m, &p, &k );
      x = k * p;
      cnt = 1;
      while ( 2 * cnt <= (n-1)*(m-1) ) {
        x = x * x;
        x %= 10007;
        cnt *= 2;
      }
      for ( j = cnt; j < (n-1)*(m-1); j ++ ) {
        x *= k;
        x *= p;
        x %= 10007;
      }
      y = p;
      cnt = 1;
      while ( 2 * cnt <= n+m-1 ) {
        y = y * y;
        y %= 10007;
        cnt *= 2;
      }
      for ( j = cnt; j < n+m-1; j ++ ) {
        y = y * p;
        y %= 10007;
      }
      x = ( x * y ) % 10007;
      fprintf ( fout, "%d\n", x );
    }
    return 0;
}