Cho \(2\) dãy số nguyên độ dài \(k\) \((1 \le k \le 10)\) là \(b_1,b_2...,b_k\) và \(c_1,c_2,...,c_k\) \((0 \le b_i, c_i \le 10^9)\). Dãy số \(a\) được xác định như sau:

• \(a_i = b_i\) (với \(1 \le i \le k\))
• \(a_i = c_1 \times a_{i-1} + c_2 \times a_{i-2} ... +c_k \times a_{i-k}\) \((i \gt k)\)

Yêu cầu

• Tính \(a_n\) với \(n \le 10^9\). Đáp án in theo modulo \(10^9\)

Dữ liệu đầu vào:

• 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_j \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_j \le 10^9\), mỗi số cách nhau một dấu cách.
• Dòng \(4\): chứa số \(n\) \((1 \le n \le 10^9)\)

Dữ liệu đầu ra:

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

Input 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 1

8
714
257599514