[SDOI2008]递归数列

题号：NC20320
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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

对于i <= k：a_i = b_i

对于i > k: a_i = c₁a_i-1 + c₂a_i-2 + ... + c_ka_i-k

其中b_j和 c_j （1<=j<=k）是给定的自然数。写一个程序，给定自然数m <= n, 计算a_m + a_m+1 + a_m+2 + ... + a_n, 并输出它除以给定自然数p的余数的值。

由四行组成。
第一行是一个自然数k。
第二行包含k个自然数b₁, b₂,...,b_k。
第三行包含k个自然数c₁, c₂,...,c_k。
第四行包含三个自然数m, n, p。

仅包含一行：一个正整数，表示(a_m + a_m+1 + a_m+2 + ... + a_n) mod p的值。

示例1

复制

2
1 1
1 1
2 10 1000003

复制

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