H. Эпическая свёртка
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны два массива $$$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$$$.

Примеры
Входные данные
2 2 3
0 1
0 1
Выходные данные
3
Входные данные
3 4 1
1 1 1
1 1 1 1
Выходные данные
12
Входные данные
2 3 3
1 2
3 4 5
Выходные данные
65652
Примечание

В первом примере единственное ненулевое слагаемое соотвествует $$$i = 1$$$, $$$j = 1$$$ и равно $$$1 \cdot 1 \cdot 3^1 = 3$$$.

Во втором примере все слагаемые равны $$$1$$$.