#include <bits/stdc++.h>
#define DIM 1010
#define MOD 10007
using namespace std;

ifstream fin ("matrice5.in");
ofstream fout ("matrice5.out");
int dp[DIM][DIM];
int t,n,m,k,p,i,j;

int lg_put (int a, int b){
    if (!b)
        return 1;
    int nr = lg_put (a,b/2);
    if (b&1)
        return 1LL * nr * nr % MOD * 1LL * a % MOD;
    return 1LL * nr * nr % MOD;
}

int main (){

    /// dp[i][j] - nr de moduri de a forma un sir de i elemente care sa aiba suma divizbila cu j

    for (i=1;i<=1000;i++)
        dp[1][i] = 1;

    for (i=2;i<=1000;i++)
        for (j=1;j<=1000;j++)
            dp[i][j] = dp[i-1][j] * j % MOD;

    fin>>t;
    for (;t--;){
        fin>>n>>m>>p>>k;
        int sol = lg_put (dp[m][k],n-1);
        sol =  1LL * sol * lg_put (p,n*m) % MOD;
        fout<<sol<<"\n";
    }



    return 0;
}