Vòi Phun Nước

Farmer John có một cánh đồng hình vuông kích thước $(N-1)\times (N-1)$, với góc tây nam tại $(0,0)$ và góc đông bắc tại $(N-1,N-1)$. Trên cánh đồng có đúng $N$ vòi phun nước hai chiều đặt tại các tọa độ nguyên.

Mỗi vòi phun nước đặt tại tọa độ $(i,j)$ hoạt động như sau:

• Tưới nước tất cả các điểm $(x,y)$ thỏa $x\ge i$ và $y\ge j$ (vùng đông bắc).
• Bón phân tất cả các điểm $(x,y)$ thỏa $x\le i$ và $y\le j$ (vùng tây nam).

Một điểm $(x,y)$ với $0\le x,y\le N-1$ được coi là hợp lệ nếu nó vừa được tưới nước bởi ít nhất một vòi phun nước, vừa được bón phân bởi ít nhất một vòi phun nước.

Biết rằng mỗi hàng và mỗi cột đều có đúng một vòi phun nước (tức là các tọa độ $x$ của các vòi tạo thành một hoán vị của $\{0,1,\dots ,N-1\}$, và tương tự với các tọa độ $y$).

Hãy đếm số hình chữ nhật có các cạnh song song với trục tọa độ, có diện tích dương, với tất cả bốn góc đều là điểm hợp lệ (có tọa độ nguyên), và tất cả các điểm nguyên bên trong và trên biên của hình chữ nhật đều là điểm hợp lệ.

Nói cách khác, đếm số cặp điểm nguyên $(x_1,y_1)$ và $(x_2,y_2)$ với $0\le x_1<x_2\le N-1$ và $0\le y_1<y_2\le N-1$ sao cho toàn bộ hình chữ nhật $[x_1,x_2]\times [y_1,y_2]$ chỉ gồm các điểm hợp lệ.

Dữ liệu vào

• Dòng đầu tiên: số nguyên $N$ ($1\le N\le {10}^5$).
• $N$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $i$ và $j$ ($0\le i,j\le N-1$) là tọa độ của một vòi phun nước.
• Đảm bảo mỗi hàng và mỗi cột có đúng một vòi phun nước.

Dữ liệu ra

In ra một số nguyên duy nhất: số hình chữ nhật hợp lệ, lấy modulo ${10}^9+7$.

Ràng buộc

• $1\le N\le {10}^5$
• Các vòi phun nước tạo thành một hoán vị: mỗi hàng và mỗi cột có đúng một vòi.

Ví dụ

Ghi chú

Đây là bài USACO 2018 January Platinum, bài 3.

Một hình chữ nhật $[x_1,x_2]\times [y_1,y_2]$ (với $x_1<x_2$, $y_1<y_2$) hợp lệ khi và chỉ khi với mỗi cột $x\in [x_1,x_2]$, tập hợp các $y$ hợp lệ trong cột đó chứa toàn bộ đoạn $[y_1,y_2]$.