[SDOI2008] 递归数列
题目描述
一个由自然数组成的数列按下式定义:
对于 $i \le k$:$a_{i}= b_{i}$。
对于 $i > k$:$a_{i}= \sum_{j=1}^{k}{c_{j} \times a_{i-j}}$。
其中 $b_{1\dots k}$ 和 $c_{1\dots k}$ 是给定的自然数。
写一个程序,给定自然数 $m \le n$,计算 $\left( \sum_{i=m}^{n}{a_{i}} \right) \bmod p$。
输入输出格式
输入格式
第一行一个自然数 $k$。
第二行 $k$ 个自然数 $b_{1},b_{2},\dots,b_{k}$。
第三行 $k$ 个自然数 $c_{1},c_{2},\dots,c_{k}$。
第四行三个自然数 $m,n,p$。
输出格式
一行一个正整数,表示 $\sum_{i=m}^{n}{a_{i}} \mod p$ 的值。
输入输出样例
输入样例 #1
2
1 1
1 1
2 10 1000003
输出样例 #1
142
说明
对于 $20\%$ 的数据,$n \le 10^{6}$。
对于另外 $30\%$ 的数据,$k=1$。
对于 $100\%$ 的数据,$1 \le k \le 15$,$1 \le m \le n \le 10^{18}$,$0 \le b_{i},c_{i} \le 10^{9}$,$p \le 10^{8}$。