#P4221. JOI2012 kangaroo

    ID: 3436 传统题 1000ms 256MiB 尝试: 84 已通过: 46 难度: 8 上传者: 标签>CF2500提高+/省选-二分图建模二分查找计数 DP前后缀状态分解Pascal 递推排列数计算

JOI2012 kangaroo

题目描述

澳洲猴和澳洲袋鼠是好朋友,他们经常在一起交流拳♂击,摔♂跤的经验。

众所周知,澳洲袋鼠的胸前有一个袋子,我们认为一个澳洲袋鼠的体积为 AiA_i,那么它的袋子的大小就是 BiB_i,显然 BiB_i 是严格小于 AiA_i 的,当然如果有东西装在这个袋鼠的袋子里面,那么袋鼠的体积仍然是 AiA_i。

某一次,澳洲猴在摔♂跤比赛中赢了袋鼠,于是,袋鼠答应澳洲猴来做一个游戏。这个游戏是这样的:全程都是澳洲猴操作,每次他可以选择一个袋鼠 ii 放到袋鼠 jj 的袋子里,但是这要满足:

  1. 袋鼠 ii 目前不在其他袋鼠的袋子里;
  2. 袋鼠 jj 目前袋子里没有其他袋鼠。

澳洲猴每次会将这 nn 个袋鼠操作到不能操作为止,它想求出最终状态一共有多少可能,由于数字很大,请模 109+710^9+7 输出。

输入格式

输入的第一行为 nn。

接下来 nn 行是 Ai,BiA_i,B_i,表示每个袋鼠的大小和它的袋子大小。

输出格式

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

样例

5
4 3
3 1
6 5
2 1
4 2
4

样例说明

  1. 将袋鼠 44 放入袋鼠 33;
  2. 将袋鼠 44 放入袋鼠 11,将袋鼠 11 放入袋鼠 33;
  3. 将袋鼠 44 放入袋鼠 11,将袋鼠 22 放入袋鼠 33;
  4. 将袋鼠 44 放入袋鼠 11,将袋鼠 55 放入袋鼠 33。

数据规模与约定

对于 100%100\% 的数据:n≤300n\le 300,1≤Bi<Ai≤1091\le B_i<A_i\le 10^9。