SEQ - Recursive Sequence


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 an for given n and output it modulo 109.

Input

On the first row there is the number C of test cases (equal to about 1000).
Each test contains four lines:

k - number of elements of (c) and (b) (1 <= k <= 10)
b1,...,bk - k natural numbers where 0 <= bj <= 109 separated by spaces
c1,...,ck - k natural numbers where 0 <= cj <= 109 separated by spaces
n - natural number (1 <= n <= 109)

Output

Exactly C lines, one for each test case: an modulo 109

Example

Input:
3 
3 
5 8 2 
32 54 6 
2 
3 
1 2 3 
4 5 6 
6 
3 
24 354 6 
56 57 465 
98765432

Output:
8 
714 
257599514

hide comments
codephilic: 2020-09-28 13:36:42

@vimi if we use dp then it will give tle use Matrix Exponentiation concept bcz its time complexity is O(k^3 Logn)

horro: 2020-07-27 21:17:08

Standard Matrix Exponentiation problem!!!

coder_619: 2020-07-20 01:22:09

Ac In 2nd Go.....:)

Last edit: 2020-07-20 01:23:31
rohitkk074: 2020-06-25 09:54:44

@abhi i made the same mistake, was doing % (1e9+7)
Read the question clearly, and be cautious of overflow

abhj: 2020-06-25 00:52:12

1e9 modulo kaun karta hai? Debug karne main adha ghanta chala gaya

souravbhadra03: 2020-06-15 07:55:06

Accepted
Hints:
Use Matrix Exponentiation and Modular Arithmetic

cs215100: 2020-05-20 21:35:01

tle in java. same code ac in c++.

jaybatra: 2020-05-02 18:48:59

can someone explain when I used python 3 it gives TLE but when i used C++ using same logic of matrix exponentiation it passed all the test cases why?

jaybatra: 2020-05-01 10:46:53

I have tried the question using python 3 it is passing the given examples but at the time of submitting it is giving TLE can someone help?

vimi: 2020-04-25 20:36:32

can we apply DP with some memoization? because surely we have overlapping subproblems


Added by:PaweĊ‚ Dobrzycki
Date:2005-04-29
Time limit:0.5s-3s
Source limit:8196B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:IV Podlasian Contest in Team Programming