Một biểu đồ cột (histogram) được xây dựng từ ~n~ cột (bins) liền kề nhau đặt trên trục hoành. Cột thứ ~i~ (tính từ trái sang) có chiều cao ~h_i~ và chiều rộng ~w_i~ (~h_i, w_i~ là các số nguyên).

Chúng ta đang quan tâm đến việc xác định các "vùng dữ liệu" (data regions) hình chữ nhật bên trong biểu đồ này. Một hình chữ nhật được định nghĩa là một "vùng dữ liệu hợp lệ" nếu thỏa mãn các điều kiện sau:

• Các cạnh của nó song song với các trục tọa độ (ngang hoặc dọc) và có độ dài là một số nguyên;

• Khoảng cách từ cạnh dưới của hình chữ nhật đến trục hoành ~(y=0)~ là một số nguyên;

• Khoảng cách từ cạnh trái của hình chữ nhật đến trục tung ~(x=0)~ là một số nguyên;

• Hình chữ nhật phải nằm hoàn toàn bên trong (hoặc trên đường viền) của các cột biểu đồ.

Yêu cầu: tính tổng số lượng các vùng dữ liệu hợp lệ. vì số này có thể rất lớn, hãy in ra kết quả sau khi chia lấy dư cho ~10^9+7~.

Input

• Dòng đầu tiên gồm một số nguyên dương ~n~ ~(1 \le n \le 10^5)~, số lượng cột của biểu đồ;

• Dòng thứ hai chứa ~n~ số nguyên dương cách nhau bởi dấu cách, số thứ ~i~ là chiều cao ~h_i~ ~(1 \le h_i \le 10^9)~;

• Dòng thứ ba chứa ~n~ số nguyên dương cách nhau bởi dấu cách, số thứ ~i~ là chiều rộng ~w_i~ ~(1 \le w_i \le 10^9)~.

Output

Một dòng duy nhất là kết quả của bài toán.

Scoring

Sample Input 1

2
1 2
1 2

Sample Output 1

12