Competitions

# Recursive Sequence

Sequence ai of integer numbers is defined as follows:

ai = bi (for ik)
ai = c1ai-1 + c2 ai-2 + ... + ck ai-k (for i > k)

where bj and cj (1jk) are given integer numbers. Your task is to compute an for given n and output it modulo 109.

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) (1k10);

b1,...,bk (0bj109) - k integers separated by spaces;

c1, ..., ck (0cj109) - k integers separated by spaces;

n - natural number (1n109).

Output

Exactly t lines, one for each test case: an modulo 109.

Time limit 1 second
Memory limit 64 MiB
Input example #1
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 example #1
8
714
257599514