题目描述

每天，大量集装箱通过船只运抵 JOI 港口，随后由卡车运往全国各地。

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

出于安全考虑，当集装箱由船只运抵时，我们必须将其放置在其中一个区域的顶部；若该区域已有集装箱，则必须将其叠放在已有集装箱的上方。当集装箱由卡车运走时，我们必须从其中一个区域的顶部取走集装箱。

今天，将有 $N$ 个集装箱运抵 JOI 港口，且所有集装箱最终都将由卡车运走。

你的任务是管理 JOI 港口的设施。对于每个集装箱，你已知其到达时间和离开时间。请编写一个程序，计算满足上述条件的堆放与取走集装箱的方式总数，结果对 $1\,000\,000\,007$ 取模。

任务

给定运抵 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$ 取模。

4
1 3
2 5
4 8
6 7

4

3
1 4
2 5
3 6

0

5
1 4
2 10
6 9
7 8
3 5

8

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

16

提示

样例 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。

数据范围

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

• $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, \cdots, A_N, B_1, \cdots, B_N$ 互不相同。

子任务

共有 4 个子任务。每个子任务的得分及附加约束如下：

子任务 1 [10 分]

• $N \le 20$。

子任务 2 [12 分]

• $N \le 2\,000$。

子任务 3 [56 分]

• $N \le 100\,000$。

子任务 4 [22 分]

无额外约束。

翻译由 Qwen3-235B 完成