Bác nông dân John có một cánh đồng lớn và đang cân nhắc trồng ngô ngọt trên một phần cánh đồng. Sau khi khảo sát, ông nhận thấy cánh đồng là một hình vuông kích thước \((N-1) \times (N-1)\). Góc tây nam có tọa độ \((0,0)\) và góc đông bắc có tọa độ \((N-1,N-1)\).

Tại một số tọa độ nguyên có các vòi phun hai đầu, mỗi vòi phun cả nước lẫn phân bón. Một vòi phun hai đầu tại tọa độ \((i,j)\) phun nước lên phần cánh đồng ở phía bắc và phía đông của nó, đồng thời phun phân bón lên phần cánh đồng ở phía nam và phía tây của nó. Cụ thể, nó tưới nước cho mọi tọa độ thực \((x,y)\) thỏa mãn \(N \geq x \geq i\) và \(N \geq y \geq j\), đồng thời bón phân cho mọi tọa độ thực \((x,y)\) thỏa mãn \(0 \leq x \leq i\) và \(0 \leq y \leq j\).

Bác nông dân John muốn trồng ngô ngọt trong một hình chữ nhật nào đó trên cánh đồng, có các cạnh song song với các trục tọa độ và tọa độ các đỉnh đều là số nguyên. Tuy nhiên, để ngô ngọt phát triển, mọi điểm trong hình chữ nhật đều phải vừa được tưới nước vừa được bón phân bởi các vòi phun hai đầu. Và tất nhiên, hình chữ nhật phải có diện tích dương, nếu không bác nông dân John sẽ không thể trồng được cây ngô nào trong đó!

Hãy giúp bác nông dân John xác định số hình chữ nhật có diện tích dương mà ông có thể trồng ngô ngọt. Vì số này có thể rất lớn, hãy in ra phần dư của nó theo \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(N\), kích thước của cánh đồng (\(1 \leq N \leq 10^5\)).

Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên cách nhau bởi dấu cách. Nếu hai số đó là \(i\) và \(j\), với \(0 \leq i,j \leq N-1\), chúng biểu thị một vòi phun đặt tại \((i,j)\).

Dữ liệu đảm bảo có đúng một vòi phun trong mỗi cột và đúng một vòi phun trong mỗi hàng. Nói cách khác, không có hai vòi phun nào có cùng tọa độ \(x\), và không có hai vòi phun nào có cùng tọa độ \(y\).

Dữ liệu ra

In ra một số nguyên duy nhất: số hình chữ nhật có diện tích dương được tưới nước và bón phân hoàn toàn, lấy phần dư theo \(10^9+7\).

Ví dụ

5
0 4
1 1
2 2
3 0
4 3

21

Nguồn

USACO 2018 January Contest, Platinum — Sprinklers

Tác giả bài toán: Dhruv Rohatgi.