本题中约定 $0^0=1$。

Snuke 使用动态规划解决了一道题目。具体来说，她设计了如下递推式： $$F(i,j)=\{\begin{array}{ll}0,& \text{if }i=0\text{;}\\ f_i,& \text{if }i>0\text{ and }j=0\text{;}\\ aF(i-1,j)+bF(i,j-1)+c,& \text{if }i>0\text{ and }j>0\text{.}\end{array}$$ 其中 $i,j$ 是非负整数，$a,b,c$ 是给定的常数，$f_i$ 是给定的数列。

Snuke 需要求出 $F(n,m)$，所以她对于 $1\le i\le n,1\le j\le m$ 计算了 $F(i,j)$，这些值形成了一个 $n\times m$ 的矩阵。

Takahashi 希望你告诉她这个矩阵。为了避免过多的输出，你只需要输出这个矩阵的哈希值。

具体来说，给定整数 $h$ 和质数 $p$，你需要输出 $$(\sum _{i=1}^n\sum _{j=1}^{m}F(i,j)h^{(i-1)m+(j-1)})modp$$ 的值。

输入格式

从标准输入读入数据。

第一行输入一个整数 $T$，表示子任务编号。

第二行输入四个整数 $n,m,h,p$。

第三行输入三个整数 $a,b,c$。

第四行输入 $n$ 个整数 $f_1,\dots ,f_n$。

输出格式

输出到标准输出。

输出一行，包含一个整数，表示矩阵的哈希值。

样例一

input

1
2 2 2 998244353
2 1 1
0 1

output

93

explanation

题目描述中提到的矩阵是 $\left(\begin{array}{cc}1& 2\\ 4& 9\end{array}\right)$，其哈希值为 $$1\times 2^0+2\times 2^1+4\times 2^2+9\times 2^3=93.$$

样例二

input

2
9 100000 5 998244353
5 4 7
6 5 6 9 3 7 4 5 2

output

623270548

样例三

input

3
9 1000000000 5 235497281
5 0 7
6 5 6 9 3 7 4 5 2

output

211538270

限制及约定

对于所有数据，保证：

• $1\le n\le {10}^6$
• $1\le m\le {10}^9$
• ${10}^8\le p\le {10}^9$，$p$ 是质数
• $0\le h,a,b,c,f_i<p$

时间限制：$2\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载