Balázs có hàng rào đẹp nhất thị trấn. Hàng rào gồm \(N\) đoạn liền kề nhau; mỗi đoạn là một hình chữ nhật dựng đứng trên mặt đất. Đoạn thứ \(i\) có chiều cao nguyên \(h_i\) và chiều rộng nguyên \(w_i\).

Ta cần đếm số hình chữ nhật đẹp nằm trên hàng rào. Một hình chữ nhật được gọi là đẹp nếu:

• Các cạnh nằm ngang hoặc thẳng đứng và có độ dài nguyên.
• Khoảng cách từ hình chữ nhật đến mặt đất là số nguyên.
• Khoảng cách từ hình chữ nhật đến mép trái của đoạn hàng rào đầu tiên là số nguyên.
• Toàn bộ hình chữ nhật nằm trên các đoạn hàng rào.

Hãy tính số hình chữ nhật đẹp. Vì kết quả có thể rất lớn, hãy in phần dư khi chia cho \(10^9+7\).

Dữ liệu vào

Dòng đầu gồm số nguyên \(N\), là số đoạn của hàng rào.

Dòng thứ hai gồm \(N\) số nguyên \(h_i\), lần lượt là chiều cao các đoạn.

Dòng thứ ba gồm \(N\) số nguyên \(w_i\), lần lượt là chiều rộng các đoạn.

Dữ liệu ra

In một số nguyên duy nhất là số hình chữ nhật đẹp modulo \(10^9+7\).

Ví dụ

2
1 2
1 2

12

Giải thích

Hình dạng hàng rào trong ví dụ:

Có \(5\) hình chữ nhật đẹp có hình dạng sau:

Có \(3\) hình chữ nhật đẹp có hình dạng sau:

Có \(1\) hình chữ nhật đẹp có hình dạng sau:

Có \(2\) hình chữ nhật đẹp có hình dạng sau:

Có \(1\) hình chữ nhật đẹp có hình dạng sau:

Ràng buộc

• \(1\le N\le 10^5\).
• \(1\le h_i,w_i\le 10^9\) với mọi \(i\).

Phân nhóm

1. \(0\) điểm: Bộ dữ liệu mẫu.
2. \(12\) điểm: \(N\le50\), \(h_i\le50\) và \(w_i=1\) với mọi \(i\).
3. \(13\) điểm: \(h_i\in\{1,2\}\) với mọi \(i\).
4. \(15\) điểm: Mọi \(h_i\) bằng nhau.
5. \(15\) điểm: \(h_i\le h_{i+1}\) với mọi \(1\le i<N\).
6. \(18\) điểm: \(N\le1000\).
7. \(27\) điểm: Không có ràng buộc nào khác.