题目描述

题目译自 USACO 2018 January Contest, Platinum Problem 3. Sprinklers

农夫约翰有块田，这块田可视为一个 $N×N$ 的正方形网格。西南角为 $(0,0)$，东北角为 $(N-1, N-1)$。
在某些格子中有双头喷头，每一个都能够同时喷洒水和肥料。一个位于 $(i,j)$ 的双头喷头会

• 将水洒在所有满足 $N≥x≥i,$ $N≥y≥j$ 的格子 $(x,y)$ 上；
• 将肥料洒在所有满足 $0≤x≤i$ 和 $0≤y≤j$ 的格子 $(x,y)$ 上。

农民约翰想在这块田里划分出一个矩形种甜玉米。矩形的边不能把格子切开。矩形内所有格子都必须能由双头喷头灌溉和施肥。
求划分矩形的方案数。由于这个数字可能很大，所以输出对 $10^9 + 7$ 取模。

输入格式

第一行包含一个整数 $N$，表示农场的大小。
接下来的 $N$ 行，每行有两个由空格分隔的整数 $i, j$。这表示有一个双头喷头位于 $(i, j)$。
保证每列都有一台喷头，每排正好有一台喷头。换句话说，没有两个喷头有相同的横坐标或纵坐标。

输出格式

输出包含一行，表示方案数，对 $10^9+7$ 取模。

5
0 4
1 1
2 2
3 0
4 3

21

数据范围与提示

$1≤N≤10^5, 0≤i, j≤N-1$。