#include <fstream>

using namespace std;
ifstream cin("matrice5.in");
ofstream cout("matrice5.out");

const long long MOD = 1e4+7;

long long fast_pow(int b,int p)
{
    if(p==0)
        return 1;
    else if(p%2==0)
    {
        long long r = fast_pow(b,p/2);
        return r*r%MOD;
    }
    return (long long)fast_pow(b,p-1)*b%MOD;

}

int main()
{
    int t;
    cin>>t;

    while(t--){
        int n,m,p,k;
        cin>>n>>m>>p>>k;
        cout<<fast_pow(p,n*m)*fast_pow(k,(m-1)*(n-1))%MOD<<'\n';
    }

    return 0;
}