UOJ Logo Universal Online Judge

UOJ

#420. 【集训队作业2018】矩形

附件下载 统计

本题中约定 $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$
子任务编号$n \le$$m \le$特殊性质分值依赖的子任务
1$1000$$1000$$p = 998244353$5
2$10^5$$10^5$241
3$10^6$$10^9$$b = 0$10
4$c = 0$28
5$f_i = 0$30
631, 2, 3, 4, 5

时间限制:$2\texttt{s}$

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

下载

样例数据下载