题目描述

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

• 对于 $i \leq k$：$a_{i} = b_{i}$；
• 对于 $i > k$：$a_{i} = c_{1}a_{i-1} + c_{2}a_{i-2} + ... + c_{k}a_{i-k}$。

其中 $b_{j}$ 和 $c_{j}$（$1 \leq j \leq k$）是给定的自然数。写一个程序，给定自然数 $m \leq n$, 计算 $a_{m} + a_{m+1} + a_{m+2} + ... + a_{n}$, 并输出它除以给定自然数 $p$ 的余数的值。

输入格式

由四行组成。

第一行是一个自然数 $k$。

第二行包含 $k$ 个自然数 $b_{1}, b_{2},...,b_{k}$。

第三行包含 $k$ 个自然数 $c_{1}, c_{2},...,c_{k}$。

第四行包含三个自然数 $m, n, p$。

输出格式

仅包含一行：一个正整数，表示 $(a_{m} + a_{m+1} + a_{m+2} + ... + a_{n}) \bmod p$ 的值。

2
1 1
1 1
2 10 1000003

142

数据规模与约定

• 对于 $100\%$ 的测试数据：$1 \leq k \leq 15$，$1 \leq m \leq n \leq 10^18$。

题目来源

没有写明来源