## 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 > kk108: 2021-11-24 19:52:06 why my code is giving wrong answer? [NG]: Read the footer. Last edit: 2021-11-24 21:15:16 divyn: 2021-08-29 14:12:00 my solution is working fine on local machine, while submitting i am getting runtime error SIGKILL. Last edit: 2021-08-29 14:13:16 rgalpha: 2020-12-22 13:11:26 Ensure that the returned answer is positive. One way is to use ((b-a)%p+p)%p. shantanu_23: 2020-07-20 12:48:01 Try Modular Arithematic. The complexity should be K^3log(N) hetp111: 2019-12-22 10:21:00 Nice one...! Last edit: 2019-12-22 10:45:14 hvh2911: 2019-12-06 10:45:31 %I64d wrong answer ?? %lld accepted ?? sk_23: 2019-06-18 09:19:53 Same as this problem ::==> https://www.spoj.com/problems/FIBOSUM/ sanjiv1970: 2019-01-27 15:39:39 yes yes yes yes!!!!! finally got AC after a lot of patience and hardwork ankitpriyarup: 2018-12-11 14:17:00 Finally AC :) Use this testcases for debugging 3 3 12732 13444 11716 16816 14741 24282 4191 32582 12765 13 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 428712075 743869840 32253000 3 16814 14072 26922 14934 30135 17494 265514280 302014416 11559 output 690 24506000 6752 v1a9r9u8n: 2018-10-15 10:58:20 Can't we use the idea of sum of geometric progression somehow? Last edit: 2018-10-15 11:31:31

 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