SPP - Recursive Sequence (Version II)

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

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

hide comments
2024-05-14 21:15:16
An edge case is kind of annoying. B's should have had some ordering.
2021-11-24 19:52:06
why my code is giving wrong answer?
<snip>

[NG]: Read the footer.

Last edit: 2021-11-24 21:15:16
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
2020-12-22 13:11:26
Ensure that the returned answer is positive. One way is to use ((b-a)%p+p)%p.
2020-07-20 12:48:01
Try Modular Arithematic. The complexity should be K^3log(N)
2019-12-22 10:21:00
Nice one...!

Last edit: 2019-12-22 10:45:14
2019-12-06 10:45:31
%I64d wrong answer ??
%lld accepted ??
2019-06-18 09:19:53
Same as this problem ::==> https://www.spoj.com/problems/FIBOSUM/
2019-01-27 15:39:39
yes yes yes yes!!!!!
finally got AC after a lot of patience and hardwork
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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.