eolymp
bolt
Try our new interface for solving problems
Məsələlər

Ужасная формула

Ужасная формула

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Ужасная матрица — это квадратная матрица порядка n, в которой первая строка и первый столбец заданы явно, а остальные элементы вычисляются по ужасной формуле, которая, по сути, представляет собой простое рекурсивное правило.

Заданы две целочисленные последовательности l и t, обе размером n, а также целочисленные параметры a, b и c. Ужасная матрица F определяется следующим образом:

  • Первый столбец матрицы представляет собой последовательность l: F[k, 1] = l_k.

  • Первая строка матрицы представляет собой последовательность t: F[1, k] = t_k.

  • Остальные элементы рассчитываются по рекурсивной формуле:

F[i, j] = a \cdot F[i, j - 1] + b \cdot F[i - 1, j] + c

В заданной ужасной матрице найдите значение элемента 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ə

Giriş verilənləri #1
3 0 0 0
0 0 2
0 3 0
Çıxış verilənləri #1
0
Giriş verilənləri #2
4 3 5 2
7 1 4 3
7 4 4 8
Çıxış verilənləri #2
41817