Cho hai mảng số nguyên ~a~ và ~b~ đều có độ dài ~n~. Bạn hãy tính giá trị biểu thức:

$$\displaystyle \sum_{i=1}^{n}a_i^{b_i}$$

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 2 \times 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên của mảng ~a~ ~(1 \le a_i \le 10^{18})~.
• Dòng cuối cùng chứa ~n~ số nguyên của mảng ~b~ ~(1 \le b_i \le 10^{18})~.

Output

• In ra giá trị biểu thức cần tính, kết quả chia lấy dư cho ~10^9+7~.

Examples

Sample Input 1

3
1 2 3
3 2 1

Sample Output 1

8

Sample Input 2

4
3 5 3 4
5 2 3 1

Sample Output 2

299

Scoring

• Subtask ~1~ ~-~ ~24\%~ số điểm: ~a_i,b_i \le 5~
• Subtask ~2~ ~-~ ~36\%~ số điểm: ~a_i,b_i \le 50~
• Subtask ~3~ ~-~ ~28\%~ số điểm: ~a_i,b_i \le 10^9~
• Subtask ~4~ ~-~ ~12\%~ số điểm: Không có ràng buộc gì thêm