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 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)$。

输出一个整数的值即 $F_{n,n}$ 模 $10^6+3$。 感谢 @ 守望提供的翻译。

Central Europe Regional Contest 2015 Problem F