#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e4 + 7;
int t, n, m, p, k;

inline int lgput(int x, int p){
    int ans = 1, aux = x;
    for(int i = 1; i <= p ; i = i << 1){
        if((p & i)) ans = (ans * aux) % MOD;
        aux = (aux * aux) % MOD;
    }
    return ans;
}

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);
        int Sol = (lgput((k * p) % MOD, m - 1) * p) % MOD;
        Sol = (lgput(Sol, n - 1) * lgput(p, m)) % MOD;
        printf("%d\n", Sol);
    }


    return 0;
}