Problems Status Rank Problem 1141 Recurrent sequence Time Limit: 1000msMemory Limit: 65536kb Description An array which only consists of natural numbers could be defined as below : (1) for any i <= k , ai = bi ; (2) for any i > k , ai = c1*ai-1+c2*ai-2+...+ck*ai-k ; Note: bj and cj( 1<=j<=k) are natural numbers which have already been given. Given m and n( m <= n ) , please write a program to compute the result of am+am+1..+an , which is denoted by r , and the output should be the value of r mod p (p is a given natural number ) . Input The input consists of several datasets( between 1 to 100,000 ). Every data set consists of 4 lines : the first line is a natural number k ; the second line contains k natural numbers: b1 , b2 , ...,bk ; the third line contains k natural numbers : c1 , c2 , ...,ck ; the forth line contains 3 natural numbers : m , n , p . 1<=k<=15, 1<=m<=n<=1018 0<=b1,b2,...bk,c1,c2,...,ck<=109, 1<=p<=108 Output The answer to every data set in the input file should take up one line . There should be one positive integer representing the value of ( am+am+1..+an ) mod p . Sample Input ```2 1 1 1 1 2 10 1000003 1 1 2 1 3 1000003 ``` Sample Output ```142 7 ```