Frightful Formula#7777
A frightful matrix is a square matrix of order where the first row and the first column are explicitly specified, while the other elements are calculated using a frightful formula which is, actually, a simple recursive rule.
Given two integer sequences and , both of size , as well as integer parameters , and , the frightful matrix is defined as follows:
The first column of the matrix is the sequence : F[k, 1] = l_k.
The first row of the matrix is the sequence : F[1, k] = t_k.
Other elements are calculated using a recursive formula:
Given a frightful matrix, find the value of the element F[n, n] modulo 10^6 + 3.
The first line contains four integers n, a, b and c~(2 \le n \le 200000, 0 \le a, b, c \le 10^6) — the size of the matrix and the recursion parameters, as described in the problem statement.
The two following lines contain integers l_1, ..., l_n and t_1, ..., t_n, respectively (l_1 = t_1, 0 \le l_k, t_k \le 10^6).
Output a single integer — the value of F[n, n] modulo 10^6 + 3.
Example 1
Example 2