zxa had a great interest in least common multiple(i.e. LCM) recently, therefore he defined $lcm(i,j)(i,j\in N^*)$ as the smallest positive integer which is divisible by both positive integer $i$ and positive integer $j$. Moreover, for any $n(n>2)$ positive integers $\{a_1,a_2,\cdots,a_n\}$, he defined that $lcm(a_1,a_2,\cdots,a_n)=lcm(lcm(a_1,a_2,\cdots,a_{n-1}),a_n)$.
zxa gave **a prime integer $p$**, choses a positive integer $x(1 < x < p)$ as random seed and used the formula $f_0=0,f_i=f_{i-1}\cdot x+1$ to generate a sequence $\{f_1,f_2,\cdots,f_m\}$ of length $m$.
zxa is interested to know, assuming that he gave a sequence $\{a_1,a_2,\cdots,a_n\}$ of length $n$, where each $a_i$ is positive integer and $\max_{1\leq i\leq n}{a_i}=m$, then what is the value of $lcm(f_{a_1},f_{a_2},\cdots,f_{a_n})$, can you help him?
The answer may be very large, so that you only need to give the value of the answer modulo $p$.
Input
The first line contains an positive integer $T$, represents there are $T$ test cases.
For each test case:
The first line contains four positive integers $n,m,p$ and $x$.
The second line contains $n$ positive integers, represent $a_1,a_2,\cdots,a_n$.
There is a blank between each integer with no other extra space in one line.
$1\leq T\leq 1000,1 < n\leq 10^5,1\leq m\leq 10^5,1 < x < p < 2^{31},1\leq a_i\leq m,1\leq\sum{n},\sum{m}\leq10^6$
Output
For each test case, output in one line a non-negative integer, repersents the value of $lcm(f_{a_1},f_{a_2},\cdots,f_{a_n})$ modulo $p$.
