Cho 2 dãy \(a\) và \(b\) gồm \(n\) chữ số \(a_1\), \(a_2\), \(a_3\),... \(a_{n-1}\), \(a_n\) và \(b_1\), \(b_2\), \(b_3\),... \(b_{n-1}\), \(b_n\) (\(0 \leq a[i], b[i] \leq 10^9\)). Một dãy \(C\) dài vô tận được xác định theo công thức sau:

• \(c_i = a_i\) nếu \(i \leq n\)
• \(c_i = c_{i - 1} \cdot b_1 + c_{i - 2} \cdot b_2 + c_{i - 3} \cdot b_3 + \ldots + c_{i - n} \cdot b_n\) nếu \(i > n\)

Yêu cầu: Tìm \(c_k\) với \(k\) là một số nguyên cho trước (\(k \leq 10^9\)).

Input

• Dòng thứ nhất chứa số nguyên \(t\) là số lượng test (\(t \leq 10^3\)) và mỗi test bao gồm 4 dòng:
  • Dòng thứ nhất ghi 1 số nguyên \(n\) là số lượng phần tử của \(a\) và \(b\) (\(1 \leq n \leq 10\))
  • Dòng thứ 2 bao gồm \(n\) số \(a_1\), \(a_2\), \(a_3\),... \(a_{n-1}\), \(a_n\) (\(0 \leq a[i] \leq 10^9\))
  • Dòng thứ 3 bao gồm \(n\) số \(b_1\), \(b_2\), \(b_3\),... \(b_{n-1}\), \(b_n\) (\(0 \leq b[i] \leq 10^9\))
  • Dòng thứ 4 ghi 1 số nguyên \(k\) (\(1 \leq k \leq 10^9\))

Output

• Gồm \(t\) dòng, mỗi dòng là số nguyên \(c_k\) cần tìm mod cho \(10^9\).

Example

2
3
1 2 3
4 5 6
3
3
17082004 27092004 12032004
01052004 24022004 09092004
10

3
119266304