Epic Convolution

题意翻译

**题意** 给两个长度分别为 $n,m$ 的序列 $A$ 和 $B$，下标从 $0$ 开始，再给一个常数 $c$，求： $$ \text{ans} =\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{m-1}A_iB_jc^{i^2j^3}$$ 你需要输出答案对 $490019$ 取模的值。 **数据范围** $n,m \le 10^5$，$A_i,B_i \le 1000$，$c<490019$

题目描述

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} $ $ </p><p>Since it's value can be really large, print it modulo $ 490019$.

输入输出格式

输入格式

First line contains three integers $ n $ , $ m $ and $ c $ ( $ 1 \le n, m \le 100\,000 $ , $ 1 \le c < 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 $ ).

输出格式

Print one integer — value of the sum modulo $ 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

说明

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 $ .

题意翻译

**题意** 给两个长度分别为 $n,m$ 的序列 $A$ 和 $B$，下标从 $0$ 开始，再给一个常数 $c$，求： $$ \text{ans} =\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{m-1}A_iB_jc^{i^2j^3}$$ 你需要输出答案对 $490019$ 取模的值。 **数据范围** $n,m \le 10^5$，$A_i,B_i \le 1000$，$c<490019$