[Sdoi2008]递归数列
时间限制：1s 空间限制：256MB
题目描述
一个由自然数组成的数列按下式定义：
对于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的余数的值。
输入格式
由四行组成。
第一行是一个自然数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
题目来源
没有写明来源