题目描述

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

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

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

1. 袋鼠 $i$ 目前不在其他袋鼠的袋子里；
2. 袋鼠 $j$ 目前袋子里没有其他袋鼠。

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

输入格式

输入的第一行为 $n$。

接下来 $n$ 行是 $A_i,B_i$，表示每个袋鼠的大小和它的袋子大小。

输出格式

输出一行，即总共的方案数模 $10^9+7$ 的余数。

样例

5
4 3
3 1
6 5
2 1
4 2

4

样例说明

1. 将袋鼠 $4$ 放入袋鼠 $3$；
2. 将袋鼠 $4$ 放入袋鼠 $1$，将袋鼠 $1$ 放入袋鼠 $3$；
3. 将袋鼠 $4$ 放入袋鼠 $1$，将袋鼠 $2$ 放入袋鼠 $3$；
4. 将袋鼠 $4$ 放入袋鼠 $1$，将袋鼠 $5$ 放入袋鼠 $3$。

数据规模与约定

对于 $100\%$ 的数据：$n\le 300$，$1\le B_i<A_i\le 10^9$。