P4351 [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$。 感谢 @ 守望提供的翻译。

Central Europe Regional Contest 2015 Problem F