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

Snuke 使用动态规划解决了一道题目。具体来说，她设计了如下递推式： $$ F(i, j) = \begin{cases} 0, & \text{if $i = 0$;} \\ f_i, & \text{if $i > 0$ and $j = 0$;} \\ aF(i - 1, j) + bF(i, j - 1) + c, & \text{if $i > 0$ and $j > 0$.} \end{cases} $$ 其中 $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$，你需要输出 $$ \left( \sum_{i = 1}^{n} \sum_{j = 1}^{m} F(i, j) \, h^{(i - 1)m + (j - 1)} \right) \bmod p $$ 的值。

输入格式

从标准输入读入数据。

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

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

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

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

输出格式

输出到标准输出。

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

样例一

input

1
2 2 2 998244353
2 1 1
0 1

output

93

explanation

题目描述中提到的矩阵是 $\left( \begin{matrix} 1 & 2 \\ 4 & 9 \end{matrix} \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\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载