Recursive Sequence

Sequence a_i of integer numbers is defined as follows:

a_i = b_i (for i ≤ k) a_i = c_1 a_{i-1} + c_2 a_{i-2} + ... + c_k a_{i-k} (for i > k)

where b_j and c_j (1 ≤ j ≤ k) are given integer numbers. Your task is to compute a_n for given n and output it modulo 10^9.

Input

On the first row there is the number t of test cases. Each test contains four lines:

k - number of elements of (c) and (b) (1 ≤ k ≤ 10);

b_1,...,b_k (0 ≤ b_j ≤ 10^9) - k integers separated by spaces;

c_1, ..., c_k (0 ≤ c_j ≤ 10^9) - k integers separated by spaces;

n - natural number (1 ≤ n ≤ 10^9).

Output

Exactly t lines, one for each test case: a_n modulo 10^9.

Examples