SPP  Recursive Sequence (Version II)
Sequence (a_{i}) of natural numbers is defined as follows:
a_{i} = b_{i} (for i <= k)
a_{i} = c_{1}a_{i1} + c_{2}a_{i2} + ... +
c_{k}a_{ik} (for i > k)
where b_{j} and c_{j} are given natural numbers for 1<=j<=k. Your task is to compute a_{m} + a_{m+1} + a_{m+2} + ... + a_{n} for given m <= n and output it modulo a given positive integer p.
Input
On the first row there is the number C of test cases (equal to about 50).
Each test contains four lines:
k  number of elements of (c) and (b) (1 <= k <= 15)
b_{1}, ... b_{k}  k natural numbers where 0 <= b_{j} <= 10^{9} separated by spaces.
c_{1}, ... c_{k}  k natural numbers where 0 <= c_{j} <= 10^{9} separated by spaces.
m, n, p  natural numbers separated by spaces (1 <= m <= n <= 10^{18}, 1<= p <= 10^{8}).
Output
Exactly C lines, one for each test case: (a_{m} + a_{m+1} + a_{m+2} + ... + a_{n}) modulo p.
Example
Input: 1 2 1 1 1 1 2 10 1000003 Output: 142
hide comments
(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20120727 07:18:01
silly mistake __"


zy.chen:
20120326 00:29:14
"{standard input}: Assembler messages:

Added by:  Fudan University Problem Setters 
Date:  20080515 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: C99 ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Problem SEQ 