#1159. yd 与袋鼠

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

题目描述

快看!动物园里的袋鼠正在表演套娃节目!

nn 只袋鼠,第 ii 只袋鼠身体的体积是 AiA_i,口袋的容积是 BiB_i(始终有 Ai>BiA_i>B_i)。称袋鼠 ii 可以被放入袋鼠 jj 的口袋里(即有序对 (i,j)(i,j) 满足“套娃”条件),当且仅当:

  • Ai<BjA_i < B_j
  • 袋鼠 ii 现在不在任何袋鼠的口袋里
  • 袋鼠 jj 的口袋现在不包含任何袋鼠

刚开始,袋鼠们站在一排,没有相互嵌套。它们会不断选出满足套娃条件的一对袋鼠 (i,j)(i,j),之后袋鼠 ii 会跳进袋鼠 jj 的口袋里。这个操作不断进行,直至无法选出满足套娃条件的一对袋鼠为止。(注意,如果袋鼠 ii 直接或间接地包含其他袋鼠,这些袋鼠也会和 ii 一块运动。被包含的袋鼠不会增加袋鼠 ii 的体积)

由于可能某一时刻袋鼠对的选择不是唯一的,袋鼠们可以选择其中的任意一对,这就导致了可能会有很多种最终袋鼠嵌套的方案。yd 十分好奇会有多少种不同的方案,可是他数不过来,于是求助于你。由于方案数量可能很多,你只需要告诉他方案数量对 109+710^9+7 取模后的值即可。

输入格式

第一行一个正整数 nn 表示袋鼠的数量。

之后 nn 行,第 ii 行两个正整数 Ai,BiA_i,B_i 表示第 ii 只袋鼠的体积和口袋容积。

输出格式

输出一行,即方案数模 109+710^9+7 的值。

样例

样例输入1

5
4 3
3 1
6 5
2 1
4 2

样例输出1

4

解释:有四种可能的状态:

  • 袋鼠 4 被放在袋鼠 3 口袋里,其他袋鼠单独存在
  • 袋鼠 4 被放在袋鼠 1 口袋里,袋鼠 1 被放在袋鼠 3 的口袋里,其他袋鼠单独存在
  • 袋鼠 4 被放在袋鼠 1 口袋里,袋鼠 2 被放在袋鼠 3 的口袋里,其他袋鼠单独存在
  • 袋鼠 4 被放在袋鼠 1 口袋里,袋鼠 5 被放在袋鼠 3 的口袋里,其他袋鼠单独存在

样例输入2

20
7 6
7 3
10 1
7 2
10 7
10 7
8 6
3 2
5 4
7 2
3 2
10 9
9 4
7 2
8 6
5 4
8 6
7 4
10 5
9 3

样例输出2

21060

数据范围与提示

1n3001\leq n \leq 300

1Bi<Ai1091\leq B_i<A_i\leq 10^9