题目描述

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

对于 $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$ 的值。

2
1 1
1 1
2 10 1000003

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