← 返回题目

题库练习 Epic Convolution

← 上一题下一题 →

A12123 | $Epic Convolution$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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

输入 #2

3 4 1
1 1 1
1 1 1 1

输出 #2

输入 #3

2 3 3
1 2
3 4 5

输出 #3

C++ 编辑器

输入

输出