题目描述

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:

• The first column of the matrix is the sequence l:

$$F[k, 1] = lk$$

• The first row of the matrix is the sequence t:

$$F[1, k] = tk$$

• 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^6 +3$.

输入格式

The first line contains four integers n, a, b and c (2≤n≤200000, 0≤ a, b, c≤$10^6$) – the size of the matrix and the recursion parameters, as described in the problem statement.

The two following lines contain integers l1,...,ln and t1,...,tn, respectively (l1 = t1, 0≤lk, tk ≤106).

输出格式

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

题目大意

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

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

$F[k,1]=$ $l _ k$

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

$F[1,k]=$ $t _ k$

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

$F[i,j]=a \times F[i,j-1]+b \times F[i-1,j]+c$。

现在要求找求出 $F[n,n]$ 模 $10^6+3$ 的值。

输入输出格式。

输入格式：

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

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

输出格式：

输出一个整数的值即 $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

提示

Central Europe Regional Contest 2015 Problem F