## 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
``` Rajat Sharma: 2016-08-06 13:56:12 Java: will learn matrix exponentiation with recursion, linear recursive equations, how to solve these equations by converting the addition into multiplicative expressions i.e. through matrices. Deepak Singh Tomar: 2016-03-07 15:56:45 matrix_exponentiation. Thanks fushar :) minhthai: 2016-02-03 17:26:12 be careful the mod is 10^9 not 10^9 + 7 :) Ðức Tân: 2015-08-27 18:45:42 dễ vãi r0bo_dart: 2015-06-25 07:28:24 Hint: While doing matrix multiplication, DON'T do temp[][] += mod(F[][] * M[][]); instead do temp[][] = mod(temp[][] + F[][] * M[][]) costed me 3 WA's ... phew... best of luck sHaShAnK sHeKhAr: 2015-06-21 18:23:23 Nice problem to reach 150 :) i_am_looser: 2015-05-30 15:59:01 learnt something new.......... ; ) sai krishna: 2015-03-11 17:52:35 ha ha ha lot of fun in doing it:) Ace.JQK: 2014-12-16 11:53:07 multiply matrix Francky: 2014-12-02 01:44:19 I guarantee it will be hell to take the #1 ; but possible. --edit--> Impossible. Oups. Last edit: 2014-12-02 01:21:04