## 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
 < Previous 1 2 3 4 Next > 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 jainaagam96: 2020-04-24 20:41:29 i tried threw Python 3 (matrix exponentiation ) But,Giving me TLE fighter_4: 2020-04-12 07:53:24 accepted,:D hellb0y_suru: 2020-02-19 15:38:33 Matrix exponentiation !!! very basic question !!! lm10_piyush: 2020-02-15 16:37:11 damn hogya!!! if is allowed to provide the solution like here I can post it... harish_49: 2019-11-03 12:37:34 AC in 0 go !!! Nice problem devinamuljono: 2019-10-19 09:58:23 manage to get accepted after dealing with some edge case ,

 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