시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 512 MB | 195 | 76 | 43 | 37.069% |
A frightful matrix is a square matrix of order n 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 l and t, both of size n, as well as integer parameters a, b and c, the frightful matrix F is defined as follows:
F[k, 1] = lk.
F[1, k] = tk.
F[i, j] = a ∗ F[i, j − 1] + b ∗ F[i − 1, j] + c.
Given a frightful matrix, find the value of the element F[n, n] modulo 106 + 3.
The first line contains four integers n, a, b and c (2 ≤ n ≤ 200 000, 0 ≤ a, b, c ≤ 106) – the size of the matrix and the recursion parameters, as described in the problem statement.
The two following lines contain integers l1, . . . , ln and t1, . . . , tn, respectively (l1 = t1, 0 ≤ lk, tk ≤ 106).
Output a single integer – the value of F[n, n] modulo 106 + 3.
3 0 0 0 0 0 2 0 3 0
0
4 3 5 2 7 1 4 3 7 4 4 8
41817