zxa and lcm

zxa最近对最小公倍数(Least Common Multiple)产生了极大的兴趣，因此他定义$lcm(i,j)(i,j\in N^*)$表示能同时被正整数$i$与正整数$j$整除的最小正整数。此外，对于任意的$n(n>2)$个正整数$\{a_1,a_2,\cdots,a_n\}$，他定义$lcm(a_1,a_2,\cdots,a_n)=lcm(lcm(a_1,a_2,\cdots,a_{n-1}),a_n)$。

zxa给出一个质数$p$，选择了一个正整数$x(1 < x < p)$作为随机种子，并按照$f_0=0,f_i=f_{i-1}\cdot x+1$的规则生成了长度为$m$的序列$\{f_1,f_2,\cdots,f_m\}$。

zxa很好奇，如果他再给出一个长度为$n$的序列$\{a_1,a_2,\cdots,a_n\}$，保证任意$a_i$为正整数，且$\max_{1\leq i\leq n}{a_i}=m$，那么$lcm(f_{a_1},f_{a_2},\cdots,f_{a_n})$是多少，你能帮助他吗？

由于答案可能很大，你只需要给出答案对$p$取模的值即可。

第一行有一个正整数$T$，表示有$T$组数据。

对于每组数据：

第一行有四个正整数$n,m,p$和$x$。

第二行有$n$个正整数，表示$a_1,a_2,\cdots,a_n$。

每一行相邻数字之间只有一个空格。

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

对于每组数据，输出一行，包含一个非负整数，表示$lcm(f_{a_1},f_{a_2},\cdots,f_{a_n})$对$p$取模的值。

1
5 5 2333 2
1 2 3 4 5

922

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