#3231. [Sdoi2008]递归数列

题目描述

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

对于 i <= k ： a i = bi

对于 i > k: ai = c1ai-1 + c2ai-2 + ... + ckai-k

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

输入格式

由四行组成。

第一行是一个自然数 k 。

第二行包含 k 个自然数 b 1, b2,...,bk。

第三行包含 k 个自然数 c 1, c2,...,ck。

第四行包含三个自然数 m , n , p 。

输出格式

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

样例

样例输入

2  

1 1  

1 1  

2 10 1000003  

样例输出

142

数据范围与提示

对于100%的测试数据：

1<= k<=15

1 <= m <= n <= 1018