[SDOI2008]递归数列

题目描述

一个由自然数组成的数列按下式定义: 对于i <= k:ai = bi 对于i > k: ai = c1ai-1 + c2ai-2 + ... + ckai-k 其中bj 和 cj (1<=j<=k)是给定的自然数。写一个程序,给定自然数m <= n, 计算am + am+1 + am+2 + ... + an, 并输出它除以给定自然数p的余数的值。

输入输出格式

输入格式


输入文件spp.in由四行组成。 第一行是一个自然数k。 第二行包含k个自然数b1, b2,...,bk。 第三行包含k个自然数c1, c2,...,ck。 第四行包含三个自然数m, n, p。

输出格式


输出文件spp.out仅包含一行:一个正整数,表示(am + am+1 + am+2 + ... + an) mod p的值。

输入输出样例

输入样例 #1

2
1 1
1 1
2 10 1000003

输出样例 #1

142

说明

对于100%的测试数据: 1<= k <=15 1 <= m <= n <= 1018 对于20%的测试数据: 1<= k <=15 1 <= m <= n <= 106 对于30%的测试数据: k=1 1 <= m <= n <= 1018 对于所有测试数据: 0<= b1, b2,... bk, c1, c2,..., ck<=109 1 <= p <= 108