Description

定义一个矩阵 $F$，其中第一行和第一列是给定的，计算矩阵方法如下：

• 矩阵的第一列是序列 $l$：

• 矩阵的第一行是序列 $t$：

• 其他元素使用给定的递归公式进行计算：

现在要求找求出 $F_{n,n}$ 模 $10^6+3$ 的值。

Input Format

第一行包含四个整数 $n$，$a$，$b$ 和 $c(2 \le n \le 2 \times 10^5,0 \le a,b$，$c \le 10^6)$ 矩阵的大小和递归参数，如问题描述中所述。

下面两行分别包含整数 $l_1, \cdots ,l_n$ 和 $t_1, \cdots ,t_n(l_1=t_1,0 \le l_k,t_k \le 10^6)$。

Output Format

输出一个整数的值即 $F_{n,n}$ 模 $10^6+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