Ở thành phố Seoul có một con sông được gọi là sông Hàn chảy theo hướng đông-tây. Trên bờ phía bắc của sông có \(N\) trường chèo thuyền được đánh số từ \(1\) đến \(N\) theo chiều di chuyển từ đầu phía tây sang đầu phía đông của bờ sông. Tất cả các tàu của cùng một trường có màu giống hệt nhau và do đó là không thể phân biệt. Các tàu từ các trường khác nhau luôn có màu sắc khác nhau và do đó chúng luôn được phân biệt. Trường với chỉ số \(i\) có thể quyết định không gửi bất kỳ tàu nào đến lễ hội. Nhưng nếu quyết định gửi tàu đến lễ hội, trường có thể gửi một số bất kỳ từ \(a_i\) đến \(b_i\) tàu, bao gồm cả hai mút. \(\left(a_i\leq b_i\right)\)

Một điều kiện quan trọng là số lượng tàu được gửi bởi trường với chỉ số \(i\), nếu trường quyết định gửi tàu, phải lớn hơn số lượng tàu được gửi bởi bất kỳ trường với chỉ số nhỏ hơn \(i\), nếu có trường như vậy đã quyết định gửi tàu.

Task

Cho biết các số \(a_i\) và \(b_i\) đối với mỗi trường, hãy tìm số lượng tất cả các cách mà các trường có thể gửi tàu đến tham gia lễ hội với điều kiện có ít nhất một trường quyết định gửi tàu.

Input

Dòng đầu tiên của dữ liệu vào chứa một số nguyên \(N\) là số lượng trường. Dòng thứ \(i\) trong số \(N\) dòng tiếp theo chứa hai số nguyên \(a_i\) và \(b_i\). \(\left(1\leq a_i\leq b_i\leq 10^9\right)\)

Output

Đưa ra trên một dòng phần dư của phép chia số lượng tất cả các cách mà các trường có thể gửi tàu tham gia lễ hội cho \(1000000007\) \((10^9+7)\).

Ví dụ

Input

2
1 2
2 3

Output

7

Giải thích

Có \(4\) cách mà trong đó chỉ có một trường quyết định gửi tàu và \(3\) cách mà trong đó cả hai trường đều gửi tàu, do đó câu trả lời là \(7\).

Ràng buộc

• Subtask 1 (09 điểm): \(1\leq N\leq 500\) và với mọi \(1\leq i\leq N\), \(a_i=b_i\).
• Subtask 2 (22 điểm): \(1\leq N\leq 500\) và \(\sum_{1\leq i\leq N}(b_i-a_i)\leq 10^6\).
• Subtask 3 (27 điểm): \(1\leq N\leq 100\).
• Subtask 4 (42 điểm): \(1\leq N\leq 500\).