#P4451. [Cerc2015]Frightful Formula

    ID: 3656 传统题 1000ms 64MiB 尝试: 290 已通过: 56 难度: 7 上传者: 标签>难度分类提高+/省选-组合数学贡献法格路计数阶乘逆元预处理数论模逆元快速幂CF2300杂项计数问题

[Cerc2015]Frightful Formula

[CERC 2015] Frightful Formula

题目描述

给定两个长度为 nn 的整数序列 ll、tt 以及三个整数 a,b,ca,b,c,定义一个 nn 行 nn 列的矩阵 FF。行和列均从 11 开始编号。

第一列为 Fk,1=lkF_{k,1}=l_k,第一行为 F1,k=tkF_{1,k}=t_k(1≤k≤n1\le k\le n,且 l1=t1l_1=t_1)。其余元素按下式计算:

$$F_{i,j}=a F_{i,j-1}+b F_{i-1,j}+c\qquad(2\le i,j\le n).$$

求 Fn,nF_{n,n} 对 106+310^6+3 取模的结果。

输入格式

第一行四个整数 n,a,b,cn,a,b,c,其中 2≤n≤200 0002\le n\le200\,000,0≤a,b,c≤1060\le a,b,c\le10^6。

第二行 nn 个整数 l1,…,lnl_1,\ldots,l_n,第三行 nn 个整数 t1,…,tnt_1,\ldots,t_n。保证 l1=t1l_1=t_1,且 0≤lk,tk≤1060\le l_k,t_k\le10^6。

输出格式

一行一个整数,表示 Fn,n mod (106+3)F_{n,n}\bmod (10^6+3)。

样例 #1

样例输入 #1

3 0 0 0
0 0 2
0 3 0

样例输出 #1

0

样例 #2

样例输入 #2

4 3 5 2
7 1 4 3
7 4 4 8

样例输出 #2

41817