#include<cstdio>

using namespace std;

const int mod = 10007;

int t , n , m , p , k;

int raise_( int a , int n ) {

	int i , ans = 1 , p = a;
	
	for ( i = 0 ; (1 << i) <= n; ++i ) {
		if ( (1 << i) & n )
			ans = (ans * p) % mod;
		p = (p * p) % mod;
	}
	
return ans;
}

int main()
{
	freopen("matrice5.in","r",stdin);
	freopen("matrice5.out","w",stdout);
	
	scanf("%d",&t);
	
	for ( ; t -- ; ) {
		
		scanf("%d %d %d %d",&n,&m,&p,&k);
		
		int ans = raise_( k , (n - 1) * (m - 1));
		
		ans = (ans * raise_(p , n * m)) % mod;
		
		printf("%d\n",ans);
	}
	
return 0;
}