Вам даны два массива \(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\).
В первом примере единственное ненулевое слагаемое соотвествует \(i = 1\), \(j = 1\) и равно \(1 \cdot 1 \cdot 3^1 = 3\).
Во втором примере все слагаемые равны \(1\).
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
4000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач