#include <fstream>
#define mod 10007
using namespace std;
ifstream cin("matrice5.in");
ofstream cout("matrice5.out");
long long int pow(long long int base, int exp) {
  if(exp==0)
    return 1LL;
  return ((exp%2==1? base : 1LL) * pow(base*base%mod, exp/2)) % mod;
}
int main()
{
  int t,n,m,p,k;
  cin>> t;
  for(int qp=0; qp<t; qp++) {
    cin >> n >> m >> p >> k;
    cout << (pow((k*p)%mod,((n-1)*(m-1))%mod)*pow(p,n+m-1))%mod <<'\n';
  }
  return 0;
}