#include <fstream>
#include <iostream>
using namespace std;
ifstream in("matrice5.in");
ofstream out("matrice5.out");
int const modulo = 10007;
int lgpow(int a ,int b)
{
    if(b == 0)
    {
        return 1;
    }
    else if(b == 1)
    {
        return a;
    }
    else
    {
        int result = lgpow(a , b / 2);
        if(b % 2 == 0)
        {
            return (1LL * result * result) % modulo;
        }
        else
        {
            return (1LL * result * result * a) % modulo;
        }
    }
}
int main()
{
    int n, m, k, p, t, i;
    in>>t;
    for (i=1; i<=t; i++)
    {
        cout<<i<<" "<<t<<'\n';
        in>>n>>m>>p>>k;
        int result = lgpow((k * p) % modulo , (n - 1) * (m - 1));
        result = (1LL * result * lgpow(p, n+m-1)) % modulo;
        out<<result<<'\n';
    }
    return 0;
}