每天都有许多集装箱通过船只运送到 JOI 港口。它们随后被卡车运往全国各地。

JOI 港口非常狭窄。它只有两个区域可以放置集装箱。在每个区域中，我们可以垂直堆放任意数量的集装箱。

出于安全考虑，当一个集装箱由船只运抵时，我们必须将其放置在其中一个区域。如果该区域已经放置了一些集装箱，我们必须将其放在这些集装箱的顶部。当我们用卡车运走一个集装箱时，我们必须从其中一个区域的顶部取走一个集装箱。

今天，有 $N$ 个集装箱将被运送到 JOI 港口。所有集装箱都将由卡车运走。

你的任务是管理 JOI 港口的设施。对于每个集装箱，你都知道它何时到达以及何时离开。请编写一个程序，计算满足条件的放置和取走集装箱的方法数，结果对 $1\,000\,000\,007$ 取模。

输入格式

从标准输入读取以下数据。

• 第一行包含一个整数 $N$，表示运送到 JOI 港口的集装箱数量。
• 接下来的 $N$ 行中，第 $i$ 行 ($1 \le i \le N$) 包含两个空格分隔的整数 $A_i, B_i$。这意味着第 $i$ 个集装箱将在时间 $A_i$ 到达 JOI 港口，并在时间 $B_i$ 被卡车运走。

输出格式

输出一行到标准输出。输出包含满足条件的放置和取走集装箱的方法数，结果对 $1\,000\,000\,007$ 取模。

数据范围

所有输入数据满足以下条件：

• $1 \le N \le 1\,000\,000$。
• $1 \le A_i \le 2N$ ($1 \le i \le N$)。
• $1 \le B_i \le 2N$ ($1 \le i \le N$)。
• $A_i < B_i$ ($1 \le i \le N$)。
• $2N$ 个整数 $A_1, \dots, A_N, B_1, \dots, B_N$ 互不相同。

子任务

共有 4 个子任务。各子任务的分数和附加限制如下：

子任务 1 [10 分]

• $N \le 20$。

子任务 2 [12 分]

• $N \le 2\,000$。

子任务 3 [56 分]

• $N \le 100\,000$。

子任务 4 [22 分]

• 无附加限制。

样例

样例输入 1

4
1 3
2 5
4 8
6 7

样例输出 1

4

说明 1

共有 4 种放置和取走集装箱的方法。将两个区域记为 A 和 B。以下放置集装箱的方式满足条件：

• 将第 1, 2, 3, 4 个集装箱分别放入区域 A, B, A, A。
• 将第 1, 2, 3, 4 个集装箱分别放入区域 A, B, A, B。
• 将第 1, 2, 3, 4 个集装箱分别放入区域 B, A, B, A。
• 将第 1, 2, 3, 4 个集装箱分别放入区域 B, A, B, B。

样例输入 2

3
1 4
2 5
3 6

样例输出 2

0

样例输入 3

5
1 4
2 10
6 9
7 8
3 5

样例输出 3

8

样例输入 4

8
1 15
2 5
3 8
4 6
14 16
7 9
10 13
11 12

样例输出 4

16