Dọc bờ bắc sông Hàn có \(N\) trường chèo thuyền, đánh số từ \(1\) đến \(N\) theo thứ tự từ tây sang đông. Mọi thuyền của cùng một trường có cùng màu và không thể phân biệt; thuyền của hai trường khác nhau luôn có màu khác nhau.

Trường \(i\) có thể không gửi thuyền tới lễ hội. Nếu tham gia, trường này được gửi một số nguyên thuyền bất kỳ từ \(a_i\) đến \(b_i\), kể cả hai đầu mút.

Điều kiện quan trọng là: nếu trường \(i\) tham gia, số thuyền trường đó gửi phải lớn hơn số thuyền của mọi trường có chỉ số nhỏ hơn \(i\) đã tham gia.

Hãy đếm số cách các trường có thể gửi thuyền, với điều kiện có ít nhất một trường tham gia. Hai cách khác nhau nếu có một trường gửi số thuyền khác nhau hoặc chỉ tham gia trong một cách.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\).
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa hai số nguyên \(a_i,b_i\).

Dữ liệu ra

In số cách modulo \(1\,000\,000\,007\).

Ràng buộc

• \(1\le N\le500\).
• \(1\le a_i\le b_i\le10^9\).

Ví dụ

2
1 2
2 3

7

Giải thích

Có bốn cách chỉ một trường tham gia và ba cách cả hai trường tham gia, tổng cộng là bảy cách.

Phân nhóm

Nguồn

Asia-Pacific Informatics Olympiad 2016, bài Boat.