#2387. 「USACO 2018.01 Platinum」Sprinklers

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目译自 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