## 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
```

 < Previous 1 2 3 4 5 Next > ashigup11: 2021-01-16 09:06:31 AC in one go coding_sourabh: 2021-01-14 08:47:20 I really wanted to write it atleast once :P , AC in one Go (Matrix exponentiation) , Note : DP can't be used due constraints here. 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?