Problem Description

Define a matrix \( F \) where the first row and the first column are given. The matrix is calculated as follows:

• The first column of the matrix is the sequence \( l \):
  \[ F[k, 1] = l_k \]

• The first row of the matrix is the sequence \( t \):
  \[ F[1, k] = t_k \]

• Other elements are calculated using the given recursive formula:
  \[ F[i, j] = a \times F[i, j-1] + b \times F[i-1, j] + c \]

The task is to find the value of \( F[n, n] \) modulo \( 10^6 + 3 \).

Input Format

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 next two lines contain integers \( l_1, \ldots, l_n \) and \( t_1, \ldots, t_n \) respectively ( \( l_1 = t_1 \), \( 0 \le l_k, t_k \le 10^6 \) ).

Output Format

Output a single integer - the value of \( F[n, n] \) modulo \( 10^6 + 3 \).

Sample Input and Output

Sample Input #1

3 0 0 0
0 0 2
0 3 0

Sample Output #1

0

Sample Input #2

4 3 5 2
7 1 4 3
7 4 4 8

Sample Output #2

41817

Notes

Central Europe Regional Contest 2015 Problem F

见题面 Input 部分

见题面 Output 部分