Cho dãy \(a_i\) được định nghĩa như sau:

Và

Cho hai dãy \(b\) và \(c\), hãy tính phần tử thứ \(n\) của dãy \(a\) khi lấy dư cho \(10^9\).

Input

• Dòng đầu tiên chứa số nguyên \(T\) \((T \le 1000)\) là số lượng bộ test.
• Mỗi test được input theo quy tắc sau:
  • Dòng đầu là số nguyên dương \(k\) \((k \le 10)\).
  • Dòng thứ hai là \(k\) số \(b_1, b_2, \ldots, b_k\) \((0 \le b_i \le 10^9)\).
  • Dòng thứ ba là \(k\) số \(c_1, c_2, \ldots, c_k\) \((0 \le c_i \le 10^9)\).
  • Dòng cuối cùng là số nguyên dương \(n\) \((1 \le n \le 10^9)\).

Output

• Gồm \(T\) dòng là đáp án cho các test.

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