| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1141
Recurrent sequence
Time Limit: 1000ms
Memory 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 |