Radek, giám đốc công ty "Radek và những người bạn", đang cố gắng làm ngập tất cả các kệ chứa tài liệu tại công ty đối thủ "Mati và cộng sự". Để thực hiện âm mưu phá hoại hoàn hảo, anh ta đã nhờ người bạn thợ sửa ống nước Janusz lắp đặt các vòi nước nhỏ phía trên mỗi kệ.

Các kệ tại công ty "Mati và cộng sự" có thể được biểu diễn đơn giản bằng các đoạn thẳng trên mặt phẳng. Mỗi kệ là một đoạn thẳng nối giữa cặp điểm $(l_i, h_i)$ và $(r_i, h_i)$. Các vòi nước do thợ sửa ống nước lắp đặt là các điểm có tọa độ $(\frac{l_i+r_i}{2}, h_i + 0.5)$. Sàn nhà trong phòng được biểu diễn bởi trục $OX$.

Tại thời điểm vòi nước phía trên kệ thứ $i$ được mở, kệ đó sẽ bị ngập. Theo quy luật tự nhiên, nước bắt đầu chảy thẳng xuống dưới từ các đầu của kệ và có khả năng làm ngập các kệ bên dưới hoặc chảy xuống sàn nhà thông qua hệ thống thoát nước tự nhiên.

Mô phỏng dòng nước chảy sau khi mở một vòi nước trong ví dụ thứ hai.

Radek sẽ xem xét các vòi nước theo một thứ tự cố định. Tại thời điểm xem xét vòi nước thứ $i$, anh ta chỉ mở nó nếu kệ thứ $i$ chưa bị ngập.

Radek vẫn chưa quyết định thứ tự mà anh ta sẽ xem xét các vòi nước. Anh ta sẽ chọn ngẫu nhiên một trong $n!$ thứ tự, mỗi thứ tự có xác suất như nhau. Radek muốn biết trung bình anh ta sẽ phải mở bao nhiêu vòi nước.

Nhiệm vụ của bạn là trả lời câu hỏi của Radek và đưa ra kết quả modulo $10^9 + 7$. Cụ thể, giả sử kết quả là $\frac{p}{q}$, trong đó $q \neq 0$ và $\text{NWD}(p, q) = 1$. Khi đó, bạn cần in ra số $p \cdot q^{-1} \pmod{10^9 + 7}$, trong đó $q^{-1}$ là số duy nhất thuộc tập hợp $\{1, 2, \dots, 10^9 + 6\}$ sao cho $q \cdot q^{-1} \equiv 1 \pmod{10^9 + 7}$.

Có thể chứng minh rằng đối với tất cả các bộ dữ liệu thỏa mãn điều kiện bài toán, kết quả là một số hữu tỉ mà mẫu số ở dạng tối giản không chia hết cho $10^9 + 7$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số tự nhiên $n$ ($1 \le n \le 500\,000$), biểu thị số lượng kệ tại công ty của Mati.

Trong $n$ dòng tiếp theo là mô tả các kệ. Dòng thứ $i$ chứa hai số tự nhiên $l_i, r_i$ ($1 \le l_i < r_i \le 2 \cdot n$), được mô tả trong nội dung bài toán. Để đơn giản, chúng ta giả định $h_i = i$.

Bạn có thể giả định rằng tất cả các số $l_i, r_i$ đều đôi một khác nhau — các số $l_i, r_i$ tạo thành một hoán vị của các số từ $1$ đến $2 \cdot n$.

Dữ liệu ra

Dòng duy nhất của đầu ra tiêu chuẩn phải chứa một số bằng số lượng vòi nước trung bình mà Radek sẽ phải mở, modulo $10^9 + 7$.

Ví dụ

Ví dụ 1

3
4 6
1 3
2 5

2

Ví dụ 2

5
2 9
3 4
1 8
6 10
5 7

233333338

Ghi chú

Giải thích ví dụ: Hãy xem xét tất cả các thứ tự có thể mà Radek sẽ phân tích các vòi nước trong ví dụ đầu tiên:

• Với thứ tự 1, 2, 3, anh ta sẽ mở cả 3 vòi.
• Với thứ tự 1, 3, 2, anh ta sẽ mở vòi thứ nhất và thứ ba. Sau khi mở vòi thứ ba, nước cũng sẽ làm ngập kệ thứ hai, vì vậy anh ta không cần phải mở vòi thứ hai nữa.
• Với thứ tự 2, 1, 3, anh ta sẽ mở cả 3 vòi.
• Với thứ tự 2, 3, 1, anh ta sẽ mở vòi thứ hai và thứ ba. Sau khi mở vòi thứ ba, nước sẽ làm ngập kệ thứ nhất, vì vậy không cần phải mở vòi thứ nhất.
• Với thứ tự 3, 1, 2 và 3, 2, 1, anh ta chỉ mở vòi thứ ba. Sau khi mở vòi này, tất cả các kệ sẽ bị ngập, vì vậy không cần phải mở các vòi khác.

Trung bình Radek phải mở $\frac{1}{6} \cdot (3 + 2 + 3 + 2 + 1 + 1) = 2$ vòi nước.

Trong ví dụ thứ hai, trung bình Radek phải mở $\frac{91}{30}$ vòi nước. Ta có $30^{-1} \equiv 233333335 \pmod{10^9 + 7}$, do đó $91 \cdot 233333335 \equiv 21233333485 \equiv 233333338 \pmod{10^9 + 7}$.