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.</p>

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:

• 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 a recursive formula:

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 10⁶ + 3.

입력 형식

The first line contains four integers n, a, b and c (2 ≤ n ≤ 200 000, 0 ≤ a, b, c ≤ 10⁶) – the size of the matrix and the recursion parameters, as described in the problem statement.</p>

The two following lines contain integers l₁, . . . , l_n and t₁, . . . , t_n, respectively (l₁ = t₁, 0 ≤ l_k, t_k ≤ 10⁶).

출력 형식

Output a single integer – the value of F[n, n] modulo 10⁶ + 3.

예제 입력 1

3 0 0 0
0 0 2
0 3 0

예제 출력 1

0

예제 입력 2

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

예제 출력 2

41817