[CERC2015] Frightful Formula

定义一个矩阵 $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$。 感谢 @ 守望提供的翻译。

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$.

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