Cho dãy (\(a_i\)) các số tự nhiên được định như sau:

• \(a_i = b_i\) (với \(i \le k\))
• \(a_i = c_1a_{i-1} + c_2a_{i-2} + ... + c_ka_{i-k}\) (với \(i > k\))

Với \(b_i\) và \(c_i\) là các số tự nhiên cho trước (\(1\le i\le k\)). Hãy tính \(a_n \mod 10^9\), với \(n\) cho trước.

Input

• Dòng đầu tiên chứa số \(c\) là số lượng test (\(1\le c\le 1000\)). Mỗi test chứa 4 dòng:
• Dòng 1: chứa số \(k\), là số phần tử của dãy \(c\) và \(b\) (\(1 \le k \le 10\))
• Dòng 2: chứa các số \(b_1,...,b_k\) với \(0 \le b_i \le 10^9\), mỗi số cách nhau một dấu cách.
• Dòng 3: chứa các số \(c_1,...,c_k\) với \(0 \le c_i \le 10^9\), mỗi số cách nhau một dấu cách.
• Dòng 4: chứa số \(n\) (\(0 \le n \le 10^9\))

Output

• Gồm \(c\) dòng, mỗi dòng là kết quả của một test, ghi giá trị: \(a_n \mod 10^9\)

Example

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

8 
714 
257599514