#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define mod 10007

int T, N, M, P, K;

int put(int a, int p) {
    if(p == 0) return 1;
    if(p == 0) return (a % mod);

    if(p % 2 == 0) {
         int jeg = put(a, p/2);
         return (jeg * jeg) % mod;
    }
    else {
         int jeg = put(a, p/2);
         int aux = (a * jeg) % mod;
         aux = (aux * jeg) % mod;
         return aux;
    }
}

int main() {
     FILE *f1=fopen("matrice5.in", "r"), *f2=fopen("matrice5.out", "w");
     int i, j, p, q;

     fscanf(f1, "%d\n", &T);
     while(T--) {
          fscanf(f1, "%d %d %d %d\n", &N, &M, &P, &K);

          int sol = (put(K, N * M - N - M + 1) * put(P, N * M)) % mod;

          fprintf(f2, "%d\n", sol);
     }

     fclose(f1); fclose(f2);
     return 0;
}