[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
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.2ms with 1 query(s).