UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4451. [Cerc2015]Frightful Formula

Statistics 下载数据

Description

给你一个n*n矩阵的第一行和第一列,其余的数通过如下公式推出: 
F[i,j]=a*f[i,j-1]+b*f[i-1,j]+c 
求f[n][n]%(10^6+3) 

Input

第一行三个数n,a,b,c 
第二行n个数,第i个表示f[i][1] 
第三行n个数,第i个表示f[1][i] 
2<=n<=200000 
其余的数大于等于0小于等于10^6 

Output

仅一个数表示f[n][n]%(10^6+3) 

Sample Input

Sample Input1:
3 0 0 0
0 0 2
0 3 0

Sample Input2:
4 3 5 2
7 1 4 3
7 4 4 8

Sample Output

Sample Output1:
0

Sample Output2:
41817

Hint

题解:JudgeOnline/upload/201603/4451.rar

Source