← 返回题目列表

Codeforces · 1054/H

H. 史诗级卷积

中文机器翻译题面 查看原题

给定两个数组 $$$a_0, a_1, \ldots, a_{n - 1}$$$ 和 $$$b_0, b_1, \ldots, b_{m-1}$$$ 和一个整数 $$$c$$$。

计算以下总和:

$$$$$$\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} a_i b_j c^{i^2\,j^3}$$$$$$

因为它的值可能非常大,所以打印它对 $$$490019$$$ 取模。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$c$$$ ($$$1 \le n, m \le 100\,000$$$, $$$1 \le c < 490019$$$)。

下一行恰好包含 $$$n$$$ 整数 $$$a_i$$$ 并定义数组 $$$a$$$ ($$$0 \le a_i \le 1000$$$)。

最后一行包含 $$$m$$$ 整数 $$$b_i$$$ 并定义数组 $$$b$$$ ($$$0 \le b_i \le 1000$$$)。

输出

打印一个整数 — 总和以 $$$490019$$$ 为模的值。

示例

输入 #1

2 2 3
0 1
0 1

输出 #1

3

输入 #2

3 4 1
1 1 1
1 1 1 1

输出 #2

12

输入 #3

2 3 3
1 2
3 4 5

输出 #3

65652

注意

在第一个示例中,唯一的非零被加数对应于 $$$i = 1$$$、$$$j = 1$$$,并且等于 $$$1 \cdot 1 \cdot 3^1 = 3$$$。

在第二个示例中,所有被加数都等于 $$$1$$$。