一个由自然数组成的数列按下式定义：
对于 $i \le k$：$a_i= b_i$
对于 $i > k$：$a_i= c_1a_{i-1}+ c_2a_{i-2}+ ... + c_ka_{i-k}$
其中 $b_j$ 和 $c_j$（$1 \le j \le k$）是给定的自然数。写一个程序，给定自然数 $m \le 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 \le k \le 15$
$1 \le m \le n \le 10^{18}$
Comet OJ