Fency Fence
Xem dạng PDFAi cũng biết rằng ChrisDxng có hàng rào đẹp nhất trong toàn thị trấn. Nó được xây dựng từ ~N~ đoạn liền kề. Các đoạn này là các hình chữ nhật đứng sát cạnh nhau trên mặt đất. Đoạn thứ ~i~ có chiều cao là số nguyên ~h_i~ và chiều rộng là số nguyên ~w_i~.
Chúng ta cần tìm các hình chữ nhật "hợp lệ" trên hàng rào này. Một hình chữ nhật được coi là hợp lệ nếu thỏa mãn các điều kiện sau:
Các cạnh của nó nằm ngang hoặc thẳng đứng và có độ dài là một số nguyên.
Khoảng cách giữa cạnh dưới của hình chữ nhật và mặt đất là một số nguyên.
Khoảng cách giữa cạnh trái của hình chữ nhật và cạnh trái của đoạn hàng rào đầu tiên là một số nguyên.
Hình chữ nhật nằm hoàn toàn bên trong các đoạn của hàng rào.
Hỏi có tổng cộng bao nhiêu hình chữ nhật hợp lệ? Vì số lượng này có thể rất lớn, hãy in ra kết quả modulo ~10^9 + 7~.
Input
Dòng đầu tiên chứa số nguyên ~N~ (~1 \le N \le 10^5~) — số lượng đoạn của hàng rào.
Dòng thứ hai chứa ~N~ số nguyên ~h_1, h_2, \ldots, h_N~ (~1 \le h_i \le 10^9~).
Dòng thứ ba chứa ~N~ số nguyên ~w_1, w_2, \ldots, w_N~ (~1 \le w_i \le 10^9~).
Output
In ra một số nguyên duy nhất: số lượng hình chữ nhật hợp lệ modulo ~10^9 + 7~.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~12~ | ~N \le 50~, ~h_i \le 50~ và ~w_i = 1~ với mọi ~i~ |
| 2 | ~13~ | ~h_i \in \{1, 2\}~ với mọi ~i~ |
| 3 | ~15~ | ~h_1 = h_2 = \cdots = h_N~ |
| 4 | ~15~ | ~h_1 \le h_2 \le \cdots \le h_N~ |
| 5 | ~18~ | ~N \le 1000~ |
| 6 | ~27~ | Không có ràng buộc gì thêm |
Sample Input 1
2
1 2
1 2
Sample Output 1
12
Notes
Có ~6~ hình chữ nhật hợp lệ nằm hoàn toàn ở độ cao từ ~0~ đến ~1~. Các hình chữ nhật còn lại phải nằm trong đoạn thứ hai và chạm độ cao ~2~. Có ~3~ hình như vậy cao ~1~ và ~3~ hình cao ~2~. Tổng là ~6 + 3 + 3 = 12~.