Ужасная формула
Ужасная формула
Ужасная матрица — это квадратная матрица порядка n, в которой первая строка и первый столбец заданы явно, а остальные элементы вычисляются по ужасной формуле, которая, по сути, представляет собой простое рекурсивное правило.
Заданы две целочисленные последовательности l и t, обе размером n, а также целочисленные параметры a, b и c. Ужасная матрица F определяется следующим образом:
Первый столбец матрицы представляет собой последовательность l: F[k, 1] = l_k.
Первая строка матрицы представляет собой последовательность t: F[1, k] = t_k.
Остальные элементы рассчитываются по рекурсивной формуле:
В заданной ужасной матрице найдите значение элемента F[n, n] по модулю 10^6 + 3.
Giriş verilənləri
В первой строке записаны четыре целых числа n, a, b и c~(2 \le n \le 200000, 0 \le a, b, c \le 10^6) — размер матрицы и параметры рекурсии, как описано в условии задачи.
Следующие две строки содержат целые числа l_1, ..., l_n и t_1, ..., t_n соответственно (l_1 = t_1, 0 \le l_k, t_k \le 10^6).
Çıxış verilənləri
Выведите одно целое число — значение F[n, n] по модулю 10^6 + 3.
Nümunə
3 0 0 0 0 0 2 0 3 0
0
4 3 5 2 7 1 4 3 7 4 4 8
41817