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
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
ayush926: 2018-06-27 16:33:07

Matrix exponentiation. Learned a lot!

hazard_10: 2018-05-13 04:08:00

I am getting TLE on using Matrix exponentiation any hints ??

galang: 2016-09-15 17:30:09

%I64d gives wa
%lld gives ac
O_O

Yash: 2015-02-17 12:24:35

Nice Question...Good exercise for Matrix Expo :)

ISHANI: 2015-02-03 20:22:41

Simple as SEQ...

Curiosa: 2013-07-01 06:42:46

This one sample test is as useless as 'g' in lasagna. @Author Please provide some other tests.

Sandeep Singh Jakhar: 2013-01-01 06:38:45

Finally...got it

Last edit: 2013-01-01 06:39:16

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