#include <fstream>

using namespace std;

const int MOD=10007;

ifstream fin("matrice5.in");
ofstream fout("matrice5.out");

int pw(int x, int y)
{
    int ret=1;
    for(;y;y>>=1)
    {
        if(y&1) ret=(1LL*ret*x)%MOD;
        x=(1LL*x*x)%MOD;
    }
    return ret;
}

int main()
{
    int t, n, m, k, p;
    fin>>t;
    while(t--)
    {
        fin>>n>>m>>p>>k;
        fout<<1LL*pw(k, (n-1)*(m-1)%MOD)*pw(p, n*m%MOD)%MOD<<"\n";
    }
    fin.close();
    fout.close();
}