#include <fstream>
using namespace std;
#define Mod 10007

int Power(int n,int p) {
    if (p == 0) return 1;
    if (p&1) return 1LL * n * Power(1LL*n*n%Mod,p>>1) % Mod;
    return Power(1LL*n*n%Mod,p>>1);
}

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

    int t,n,m,p,k;
    fin >> t;
    while (t--) {
        fin >> n >> m >> p >> k;
        //  a1*c1 + a2*c2 + ... + am*cm = dK      this is a row
        int GoodRows_with_value_from_1_to_K = Power(k,m-1);         // a1,a2,a3...,am
        int Coefficients_with_value_from_1_to_P = Power(p,m);       // c1,c2,c3...,cm
        int GoodRows = GoodRows_with_value_from_1_to_K * Coefficients_with_value_from_1_to_P % Mod;
        int Matrix = Power(GoodRows,n-1) * Coefficients_with_value_from_1_to_P % Mod;     // we do not chose the last row
        fout << Matrix << "\n";
    }
}