## 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
 sagar_june97p: 2019-06-12 14:07:21 AC in One go!!! surajk543: 2018-10-19 14:05:29 Got Accepted Finally...YAAHOOOO>>> masterchef2209: 2018-09-07 23:30:45 AC in 1 go good question :D riyuzaki251097: 2018-08-14 23:10:21 though concept is easier to think but implementation took me hours hrsh_sengar: 2018-03-14 09:06:48 My 100th :) aruneshg: 2017-12-26 16:41:57 when to take mod amulyagaur: 2017-08-30 20:26:50 ac in 1 go babur: 2017-08-22 19:43:16 How can output of 3rd case be 257599514, this number is greater than 1e9 and so by modulo the output must be 57599514. Where am I going please help.. 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 :)

 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