Time Limit: 1000ms
Memory Limit: 65536kb
DescriptionAn 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 ) .
InputThe 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
OutputThe 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 .
2 1 1 1 1 2 10 1000003 1 1 2 1 3 1000003