P14383 [JOISC 2017] 港口设施 / Port Facility

每天，大量集装箱通过船只运抵 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$ 取模。

### 样例 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 完成