Вам даны два массива \(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\).
Выходные данные
Выведите одно число — значение суммы по модулю \(490019\).
Примечание
В первом примере единственное ненулевое слагаемое соотвествует \(i = 1\), \(j = 1\) и равно \(1 \cdot 1 \cdot 3^1 = 3\).
Во втором примере все слагаемые равны \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2 3
0 1
0 1
|
3
|
|
2
|
3 4 1
1 1 1
1 1 1 1
|
12
|
|
3
|
2 3 3
1 2
3 4 5
|
65652
|