H. Epic Convolutiontime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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.InputFirst 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).OutputPrint one integer — value of the sum modulo 490019.ExamplesInput2 2 30 10 1Output3Input3 4 11 1 11 1 1 1Output12Input2 3 31 23 4 5Output65652NoteIn 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.
Input2 2 30 10 1
Output3
['chinese remainder theorem', 'fft', 'math', 'number theory', '*3500']