CF1054H.Epic Convolution

You are given two arrays $a_0, a_1, \ldots, a_{n - 1}$ and $b_0, b_1, \ldots, b_{m-1}$, and an integer $c$.

Compute the following sum:

$$\\sum\_{i=0}^{n-1} \\sum\_{j=0}^{m-1} a\_i b\_j c^{i^2\\,j^3}$$

Since it's value can be really large, print it modulo $490019$.

给你两个数组 $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$ 取模的值。

First line contains three integers $n$, $m$ and $c$ ($1 \le n, m \le 100\,000$, $1 \le c \lt 490019$).

Next line contains exactly $n$ integers $a_i$ and defines the array $a$ ($0 \le a_i \le 1000$).

Last line contains exactly $m$ integers $b_i$ and defines the array $b$ ($0 \le b_i \le 1000$).

第一行包含三个整数 $n$、$m$ 和 $c$（$1 \le n, m \le 100\,000$，$1 \le c \lt 490019$）。

第二行包含恰好 $n$ 个整数 $a_i$，定义数组 $a$（$0 \le a_i \le 1000$）。

第三行包含恰好 $m$ 个整数 $b_i$，定义数组 $b$（$0 \le b_i \le 1000$）。

Print one integer — value of the sum modulo $490019$.

输出一个整数——该和对 $490019$ 取模的结果。

In the first example, the only non-zero summand corresponds to $i = 1$, $j = 1$ and is equal to $1 \cdot 1 \cdot 3^1 = 3$.

In the second example, all summands are equal to $1$.

在第一个例子中，唯一的非零加项对应于 $i = 1$、$j = 1$，其值为 $1 \cdot 1 \cdot 3^1 = 3$。

在第二个例子中，所有加项均等于 $1$。