“可怕矩阵”是一个 $n$ 阶方阵，其第一行和第一列是明确给出的，而其他元素则通过一个“可怕公式”（实际上是一个简单的递归规则）计算得出。

给定两个长度均为 $n$ 的整数序列 $l$ 和 $t$，以及整数参数 $a, b$ 和 $c$，可怕矩阵 $F$ 定义如下：

• 矩阵的第一列为序列 $l$： $F[k, 1] = l_k$。
• 矩阵的第一行为序列 $t$： $F[1, k] = t_k$。
• 其他元素使用递归公式计算： $F[i, j] = a * F[i, j - 1] + b * F[i - 1, j] + c$。

给定一个可怕矩阵，求元素 $F[n, n]$ 对 $10^6 + 3$ 取模后的值。

输入格式

第一行包含四个整数 $n, a, b$ 和 $c$ ($2 \le n \le 200\,000, 0 \le a, b, c \le 10^6$)，分别表示矩阵的大小和递归参数。

接下来的两行分别包含整数序列 $l_1, \dots, l_n$ 和 $t_1, \dots, t_n$ ($l_1 = t_1, 0 \le l_k, t_k \le 10^6$)。

输出格式

输出一个整数，即 $F[n, n]$ 对 $10^6 + 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