CF1054H Epic Convolution

给定两个数组 $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$ 取模的结果。

在第一个样例中，唯一的非零项对应 $i = 1$，$j = 1$，其值为 $1 \cdot 1 \cdot 3^1 = 3$。 在第二个样例中，所有项的值都等于 $1$。 由 ChatGPT 4.1 翻译