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
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
(Tjandra Satria Gunawan)(曾毅昆): 2012-12-30 10:32:11

It's very hard to get accepted with python code, My top speed C code "for now" AC in 0.05s, same algo with python 2 and python 3 but TLE (>7s)...

[Rampage] Blue.Mary: 2012-11-21 04:51:42

After solving this, try http://www.spoj.pl/problems/SPP2/

(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