SPOJ Problem Set (classical) 339. Recursive Sequence Problem code: SEQ

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 50).
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

---

Added by:	Paweł Dobrzycki
Date:	2005-04-29
Time limit:	2s
Source limit:	8196B
Languages:	All except: PERL 6
Resource:	IV Podlasian Contest in Team Programming