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: \begin{itemize} \item The first column of the matrix is the sequence $l$: $F[k, 1] = l_k$. \item The first row of the matrix is the sequence $t$: $F[1, k] = t_k$. \item Other elements are calculated using a recursive formula: \end{itemize} $$ F[i, j] = a \cdot F[i, j - 1] + b \cdot F[i - 1, j] + c $$ Given a frightful matrix, find the value of the element $F[n, n]$ modulo $10^6 + 3$. \InputFile 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)$. \OutputFile Output a single integer --- the value of $F[n, n]$ modulo $10^6 + 3$.