#P2461. [SDOI2008] 递归数列

    ID: 1469 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2008各省省选递归山东矩阵乘法

[SDOI2008] 递归数列

题目描述

一个由自然数组成的数列按下式定义:

对于 iki \le kai=bia_{i}= b_{i}

对于 i>ki > kai=j=1kcj×aija_{i}= \sum_{j=1}^{k}{c_{j} \times a_{i-j}}

其中 b1kb_{1\dots k}c1kc_{1\dots k} 是给定的自然数。

写一个程序,给定自然数 mnm \le n,计算 (i=mnai)modp\left( \sum_{i=m}^{n}{a_{i}} \right) \bmod p

输入格式

第一行一个自然数 kk

第二行 kk 个自然数 b1,b2,,bkb_{1},b_{2},\dots,b_{k}

第三行 kk 个自然数 c1,c2,,ckc_{1},c_{2},\dots,c_{k}

第四行三个自然数 m,n,pm,n,p

输出格式

一行一个正整数,表示 i=mnaimodp\sum_{i=m}^{n}{a_{i}} \mod p 的值。

2
1 1
1 1
2 10 1000003
142

提示

对于 20%20\% 的数据,n106n \le 10^{6}

对于另外 30%30\% 的数据,k=1k=1

对于 100%100\% 的数据,1k151 \le k \le 151mn10181 \le m \le n \le 10^{18}0bi,ci1090 \le b_{i},c_{i} \le 10^{9}p108p \le 10^{8}