Sequence (a_i) of natural numbers is defined as follows:

   a_i = b_i (for i ≤ k)
   a_i = c₁a_i-1 + c₂a_i-2 + ... + c_ka_i-k (for i > k)

where b_j and c_j are given natural numbers for 1 ≤ j ≤ k. Your task is to compute a_n for given n and output it modulo 10⁹.

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)
b₁ ... b_k - k natural numbers where 0 ≤ b_j ≤ 10⁹ separated by spaces
c₁ ... c_k - k natural numbers where 0 ≤ c_j ≤ 10⁹ separated by spaces
n - natural number (1 ≤ n ≤ 10⁹)

Output

Exactly C lines, one for each test case: a_n modulo 10⁹.

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