In this problem, we define $0^0 = 1$.

Snuke is solving a problem using dynamic programming. Specifically, she designed the following recurrence relation: $$ 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} $$ where $i, j$ are non-negative integers, $a, b, c$ are given constants, and $f_i$ is a given sequence.

Snuke needs to find $F(n, m)$, so she calculated $F(i, j)$ for $1 \le i \le n, 1 \le j \le m$. These values form an $n \times m$ matrix.

Takahashi wants you to tell her about this matrix. To avoid excessive output, you only need to output the hash of this matrix.

Specifically, given an integer $h$ and a prime $p$, you need to output the value of $$ \left( \sum_{i = 1}^{n} \sum_{j = 1}^{m} F(i, j) \, h^{(i - 1)m + (j - 1)} \right) \bmod p $$

Input

The input is read from standard input.

The first line contains an integer $T$, representing the subtask number.

The second line contains four integers $n, m, h, p$.

The third line contains three integers $a, b, c$.

The fourth line contains $n$ integers $f_1, \ldots, f_n$.

Output

Output to standard output.

Output a single line containing an integer, representing the hash of the matrix.

Examples

Input 1

1
2 2 2 998244353
2 1 1
0 1

Output 1

93

Note 1

The matrix mentioned in the problem description is $\left( \begin{matrix} 1 & 2 \\ 4 & 9 \end{matrix} \right)$, and its hash value is $$ 1 \times 2^0 + 2 \times 2^1 + 4 \times 2^2 + 9 \times 2^3 = 93. $$

Input 2

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

Output 2

623270548

Input 3

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

Output 3

211538270

Constraints

For all data, it is guaranteed that:

• $1 \le n \le 10^6$
• $1 \le m \le 10^9$
• $10^8 \le p \le 10^9$, $p$ is a prime
• $0 \le h, a, b, c, f_i < p$