eolymp
Competitions

Азербайджан - подготовка. Март 12

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