zxa and lcm

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

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$

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

1
5 5 2333 2
1 2 3 4 5

922 

$lcm(1,3,7,15,31)=3255$.

BestCoder Round #83