Ужасная матрица — это квадратная матрица порядка n, в которой первая строка и первый столбец заданы явно, а остальные элементы вычисляются по ужасной формуле, которая, по сути, представляет собой простое рекурсивное правило.
Заданы две целочисленные последовательности l и t, обе размером n, а также целочисленные параметры a, b и c. Ужасная матрица F определяется следующим образом:
Первый столбец матрицы представляет собой последовательность l: F[k,1]=lk.
Первая строка матрицы представляет собой последовательность t: F[1,k]=tk.
Остальные элементы рассчитываются по рекурсивной формуле:
В заданной ужасной матрице найдите значение элемента F[n,n] по модулю 106+3.
В первой строке записаны четыре целых числа n,a,b и c (2≤n≤200000,0≤a,b,c≤106) — размер матрицы и параметры рекурсии, как описано в условии задачи.
Следующие две строки содержат целые числа l1,...,ln и t1,...,tn соответственно (l1=t1,0≤lk,tk≤106).
Выведите одно целое число — значение F[n,n] по модулю 106+3.