Cho hai mảng \(A\) và \(B\) cùng có \(N\) phần tử , mảng \(A\) gồm \(a_1,a_2,a_3,\ldots,a_N\) và mảng \(B\) gồm \(b_1,b_2,b_3,\ldots,b_N\).

Yêu cầu: Hãy tính \(\left(a_1^{b_1}+a_2^{b_2}+a_3^{b_3}+\ldots+a_N^{b_N}\right)\ mod\ {10}^9\).

Input

• Dòng một là số nguyên dương \(N\) duy nhất \((1 \le N\le{10}^5)\).
• Dòng thứ hai là \(N\) phần tử của mảng \(A\), mỗi số cách nhau một khoảng trắng \((1 \le {a}_i\le{10}^5)\).
• Dòng thứ ba là \(N\) phần tử của mảng \(B\), mỗi số cách nhau một khoảng trắng \((1 \le {b}_i\le{10}^5)\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(25\%\) số điểm) : Có \(N = 1\) và \(a_i,b_i \le 8\).
• Subtask \(2\) (\(25\%\) số điểm) : Có \(b_i \le 100\).
• Subtask \(3\) (\(25\%\) số điểm) : Có \(a_1=a_2=...=a_N\).
• Subtask \(4\) (\(25\%\) số điểm) : Không có ràng buộc gì thêm.

Example

3
1 2 3
4 5 6

762