[Sdoi2008]递归数列

时间限制:1s      空间限制:256MB

题目描述

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


输入格式

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


输出格式

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


样例输入

2
1 1
1 1
2 10 1000003

样例输出

142

提示


对于100%的测试数据:
1<= k<=15
1 <= m <= n <= 1018


题目来源

没有写明来源