Problem: Naruto is a fan of numbers, he likes to play with them. This time he decided to multiply numbers and produce output. After every k elements he decides to find x^m, where x is the multiplication till k elements and m is a random number that naruto takes. Help naruto find the output. 

As answer could be large, help him, calculate value modulo w.

Input
T=number of test case
N=number of elements he will enter
K=every kth element
M=Random number
W=Modulo 
A[i]=n elements to be entered.  

Output
Output answer of each test case in one line.  

Constraint:
0<t<100
0<a[i]<10000000
1<n<101
k<100000
m<100000 
w<100000    

SAMPLE INPUT
2
5 2 2 5
1 2 3 4 5
5 2 2 5
1 2 3 4 6

SAMPLE OUTPUT
0
4

Explanation

In first case n=5,k=2,m=2,w=5;
Step 1
1
Step 2: 12=2
since k=2 therefore 2^m=2^2=4;
Step 3: 43=12
Step 4: 124=48
since k=2,therefore 48^m=48^2
step 5: 23045=11520
step 6: 11520%5=0

2nd Test case
Step 1
1
Step 2: 12=2
since k=2 therefore 2^m=2^2=4;
Step 3: 43=12
Step 4: 124=48
since k=2,therefore 48^m=48^2
step 5: 23046=13824
step 6: 13824%5=4

Solution (in PYTHON):

Solution:
def powexpo(base,ex,k):
	a=base
	re=1
	while (ex>0):
		if (ex%2==1):
			re=re*a;
			re=re%k;
		a=a*a;
		a=a%k;
		ex=ex/2;
	return re;
t=input()
while t:
	t-=1
	n,k,m,w=map(int,raw_input().split())
	a=map(int,raw_input().split())
	i=1
	ans=1
	while (i<=len(a)):
		ans=ans*a[i-1]
		ans%=w
		if (i%(k)==0):
			ans=powexpo(ans,m,w)
		i+=1
		
	print ans