## SPP - Recursive Sequence (Version II)

no tags

Sequence (ai) of natural numbers is defined as follows:

ai = bi (for i <= k)
ai = c1ai-1 + c2ai-2 + ... + ckai-k (for i > k)

where bj and cj are given natural numbers for 1<=j<=k. Your task is to compute am + am+1 + am+2 + ... + an 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)
b1, ... bk - k natural numbers where 0 <= bj <= 109 separated by spaces.
c1, ... ck - k natural numbers where 0 <= cj <= 109 separated by spaces.
m, n, p - natural numbers separated by spaces (1 <= m <= n <= 1018, 1<= p <= 108).

### Output

Exactly C lines, one for each test case: (am + am+1 + am+2 + ... + an) modulo p.

### Example

```Input:
1
2
1 1
1 1
2 10 1000003

Output:
142
```

hide comments
 < Previous 1 2 3 Next > (Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2012-07-27 07:18:01 silly mistake -__-" finally got AC... zy.chen: 2012-03-26 00:29:14 "{standard input}: Assembler messages: {standard input}:3: Fatal error: can't write /home/X0UKa0/ccazCGw4.o: No space left on device {standard input}:3: Fatal error: can't close /home/X0UKa0/ccazCGw4.o: No space left on device" ??????? What's this? After submittal , I got a "CE"...... Last edit: 2012-03-26 00:31:21

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