SPP3 - Recursive Sequence (Version III)

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

ai = bi if i ≤ k
ai = c1ai-1 + c2ai-2 + ... + ckai-k if i > k

where bj and cj are given natural numbers for 1 ≤ j k. Your task is to compute a2m + a2m+1 + a2m+2 + ... + a2n for given m n and output it modulo a given positive integer p (not necessarily prime).

Input

On the first row there is the number T of test cases (T 50).
Each following test case 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 T lines, one for each test case: (a2m + a2m+1 + a2m+2 + ... + a2n) modulo p.

Example

Input:
2
3
2 3 5
1 2 3
10 15 1000000
15
401 131 940 406 673 592 532 452 733 966 602 600 61 212 257
13 12 81 75 37 12 10 35 25 75 16 90 27 33 47
2 85704376 99999991 Output: 248783
32397016

Note

You can try the problem SPP first.


Added by:feodorv
Date:2020-04-10
Time limit:1s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2020-04-22 11:26:32 suhash
@Blue.Mary: Thanks for the response! :)
@feodorv: Oops, thanks! That did the trick. :D

Last edit: 2020-04-22 17:58:40
2020-04-22 11:06:44 [Rampage] Blue.Mary
@suhash: I think your program is too slow. My program runs for ~6 seconds for the largest possible test file (generated by myself), but get AC in ~1.2 seconds for real test file. So the time limit is not tight at all, and the real test is not so large.
2020-04-22 06:23:44 suhash
feodorv@: Could you provide some more information on the test files (if there are worst case files with T = 50 and n = 1e18) ? Not sure if I need to reduce the order of my matrix or optimise the implementation.
suhash@: There are three randomly generated input files with T=50, one with T=15 and heavy cases and small one with "corner" cases. Please, pay attention to the modulo limits. Good luck!

Last edit: 2020-04-22 16:27:24
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.