Tổng Mũ

Xem PDF

Điểm: 1000 (p) Thời gian: 0.5s Bộ nhớ: 256M Input: MUL.INP Output: MUL.OUT

Cho hai mảng \(A\)\(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\)\(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

Test 1

Input
3
1 2 3
4 5 6
Output
762

Bình luận