#include <cstdio>

#define modulo 10007

int T, N, M, P, K;

int power(int B, int P)
{
    int aux;
    
    if (P == 0) return 1;
    aux = power(B, P>>1);
    if (P&1) return (((aux*aux) % modulo) * B) % modulo;
    return (aux*aux) % modulo;
}

int main()
{
    freopen("matrice5.in","r",stdin);
    freopen("matrice5.out","w",stdout);
    
    scanf("%d", &T);
    while (T--)
    {
          scanf("%d %d %d %d", &N, &M, &P, &K);
          printf("%d\n", (power(K, (N-1)*(M-1)) * power(P, N*M)) % modulo);
    }
    
    return 0;
}