K 理事长对袋鼠产生了兴趣，并决定观察它们的行为。K 理事长正在观察 $N$ 只袋鼠。每只袋鼠都有一个口袋。袋鼠被编号为 $1, 2, \dots, N$。袋鼠 $i$ 的本体大小为 $A_i$，袋鼠 $i$ 的口袋大小为 $B_i$。口袋的大小小于该袋鼠的本体大小 ($A_i > B_i$)。

最初，没有任何袋鼠的口袋里装有其他袋鼠。袋鼠会重复执行以下操作，直到无法再进行操作为止：

如果存在一对袋鼠 $i$ 和 $j$ 满足 $A_i < B_j$，且袋鼠 $i$ 目前没有装在其他袋鼠的口袋里，同时袋鼠 $j$ 的口袋里也没有装其他袋鼠，那么袋鼠 $i$ 就会进入袋鼠 $j$ 的口袋中。此时，袋鼠 $i$ 的口袋里是否装有其他袋鼠，或者袋鼠 $j$ 是否装在其他袋鼠的口袋里，都没有关系。如果存在多组这样的 $(i, j)$，则无法确定会选择哪一组。如果袋鼠 $i$ 的口袋里装有其他袋鼠，那么里面的袋鼠会随袋鼠 $i$ 一起移动。

给定袋鼠的本体和口袋大小，求最终状态有多少种可能，结果对 $1\,000\,000\,007$ ($= 10^9 + 7$) 取模。

数据范围

• $1 \le N \le 300$
• $1 \le B_i < A_i \le 1\,000\,000\,000$

输入格式

从标准输入读取以下内容：

• 第 1 行包含一个整数 $N$。
• 接下来的 $N$ 行包含袋鼠的信息。第 $i+1$ 行 ($1 \le i \le N$) 包含两个以空格分隔的整数 $A_i$ 和 $B_i$。

输出格式

将最终状态的可能数量对 $1\,000\,000\,007$ ($= 10^9 + 7$) 取模后的结果输出到标准输出。

子任务

• 对于配分 50% 的测试数据，满足 $N \le 30$。
• 对于配分 70% 的测试数据，满足 $N \le 70$。

样例

输入格式 1

5
4 3
3 1
6 5
2 1
4 2

输出格式 1

4

说明

袋鼠 1、袋鼠 2 和袋鼠 5 可以进入袋鼠 3 的口袋。此外，袋鼠 4 可以进入袋鼠 1 或袋鼠 3 的口袋，而袋鼠 3 不能进入任何其他袋鼠的口袋。因此，最终状态有以下 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