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
riyuzaki251097: 2018-08-14 23:10:21

though concept is easier to think but implementation took me hours

aruneshg: 2017-12-26 16:41:57

when to take mod

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 :)

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

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:)


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