Epic Convolution
Contest: Mail.Ru Cup 2018 Round 1
Difficulty rating: 3500
Tags: chinese remainder theorem, fft, math, number theory

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

Input format:
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$$$).

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

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

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

Example input:
2 2 3
0 1
0 1

Example output:
3

Example input:
3 4 1
1 1 1
1 1 1 1

Example output:
12

Editorial:
The given modulo $$$490019$$$ is a prime one.
Note, that value of $$$c^{(i^2 \, j^3)}$$$, according to the Fermat's theorem, depends only on the $$$(i^2 j^3) \mod (490019 - 1)$$$.
The main idea is that we want to end up with something like polynomial $$$\sum c_t x^t$$$, where $$$t$$$ would be $$$(i^2 j^3) \mod (490019 - 1)$$$ and $$$c_t$$$ is sum of corresponding $$$a_i b_j$$$.
If we have such a polynomial, we can easily compute the final answer.
Now time to notice, that the given modulo was... a bit non standard.
Notice, that $$$phi = 490019 - 1 = 490018 = 2 \cdot 491 \cdot 499$$$.
As chinese remainder theorem suggests, $$$x \mod phi$$$ is equivalent to $$$(x \mod 2, x \mod 491, x \mod 499)$$$ (for all $$$x$$$)
And instead of multiplying resiudes modulo $$$phi$$$ we can multiply (and computing squares and cubes) the elements of this tuple pairwise.
Let's ignore the first component for a while (suppose $$$x \mod 2 = 0$$$).
Since the numbers $$$491$$$ and $$$499$$$ are prime, they have a primitive roots.
Let's compute discrete logarithms of the residues of $$$i^2$$$'s and $$$j^3$$$'s modulo $$$491$$$ and $$$499$$$.
(There is some trouble if the residue is zero, but let's skip for now).
And now we left only with multiplication.
But since we have taken log's multiplication becomes summation. So we can apply a polynomial multiplication to solve the problem.
Basically, we have two polynomials of form $$$\sum_{i,j} c_{i,j} x^i y^j$$$ (from array $$$a$$$ and array $$$b$$$), where $$$i$$$ is logarithm of residue modulo $$$491$$$ and $$$j$$$ is logarithm of residue modulo $$$499$$$.
We can multiply these polynomials with fft! A 2d polynomial is matrix of it's coefficients. A 2d fft is matrix of it's values in $$$(w^i_n, w^j_m)$$$.
One can prove, that to have 2d fft we can just apply fft on all lines and then on all columns (or vice versa).
The rest is as usual, multiply fft's values pointwise, then inverse fft and examine the result as we stated in the begining of editorial.
We need to deal with cases when residue is equal to zero modulo $$$2$$$, $$$491$$$ or $$$499$$$.
Since the timelimit was really generous we can deal with latter two just by handling all pairs $$$(i, j)$$$ where either $$$i$$$ is zero modulo $$$491$$$ or $$$499$$$ or $$$j$$$ is zero modulo $$$491$$$ or $$$499$$$ in a naive way.
This is roughly $$$nm{/}sqrt(mod)$$$ pairs which takes roughly a second with the given constraints.
Residues modulo $$$2$$$ must be handled specifically (because there are too much pairs), but it is easy since there are only two of them. Basically the end residue is $$$1$$$ only if original residues are $$$1$$$ as well.