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
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
