Hội thuyền

Tại thành phố Seoul, có một con sông tên là Han chảy theo hướng đông -- tây.
Ở bờ phía bắc của con sông, có \(N\) trường dạy chèo thuyền, được đánh số từ \(1\) đến \(N\)
theo thứ tự từ tây sang đông.

Tất cả các thuyền đến từ cùng một trường đều có cùng màu sắc và do đó không phân biệt được.
Ngược lại, các thuyền đến từ những trường khác nhau luôn có màu khác nhau và do đó phân biệt được.

Trường số \(i\) có thể chọn không gửi thuyền nào đến lễ hội.
Nếu trường số \(i\) quyết định gửi thuyền, thì số lượng thuyền được gửi phải nằm trong đoạn
\([a_i, b_i]\) (bao gồm cả \(a_i\) và \(b_i\)).

Điều kiện quan trọng là:
Nếu trường số \(i\) gửi thuyền, thì số thuyền của trường \(i\) phải lớn hơn số thuyền của
mọi trường có số thứ tự nhỏ hơn \(i\) (nếu các trường đó cũng gửi thuyền).

Biết các giá trị \(a_i\) và \(b_i\) cho mọi trường, hãy tính số cách khác nhau để các trường gửi thuyền
đến lễ hội, sao cho có ít nhất một trường gửi thuyền.

Hai cách được coi là khác nhau nếu tồn tại một trường mà số thuyền gửi đi khác nhau giữa hai cách đó.

\InputFile

• Dòng đầu chứa số nguyên \(N\) --- số lượng trường dạy chèo thuyền.
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(a_i, b_i\)
  \((1 \le a_i \le b_i \le 10^9)\).

\OutputFile

In ra một số nguyên --- số cách gửi thuyền thỏa mãn yêu cầu,
lấy phần dư khi chia cho \(1\,000\,000\,007\).

Trong tất cả các test,

• \(1 \le N \le 500\).
• \(1 \le a_i \le b_i \le 10^9\).

\Scoring

• Subtask 1 (9 điểm): \(1 \le N \le 500\), \(a_i = b_i\) với mọi \(i\).
• Subtask 2 (22 điểm): \(1 \le N \le 500\), \(\sum_{i=1}^{N} (b_i - a_i) \le 10^6\).
• Subtask 3 (27 điểm): \(1 \le N \le 100\).
• Subtask 4 (42 điểm): không có ràng buộc gì thêm.

Example

2
1 2
2 3

7