分数: 800 点
问题陈述
有 N 客户命名 1,\ldots,N 参观商店。客户 i 到达时间 A_i 并按时离开 B_i。队列顺序是 先进先出,所以 A_i 正在增加,并且 B_i 正在增加。此外,所有 A_i 和 B_i 成对不同。
在入口处有一个访客名单,可以输入他们的名字。每个顾客在到达或离开时都会在列表中的下一个位置写下他们的名字一次。到底能有多少种不同的名字顺序呢? 求计数模数 998\,244\,353.
约束
- 1 \leq N \leq 5 \cdot 10^5
- 1 \leq A_i < B_i \leq 2N
- A_i < A_{i + 1} (1 \leq i \leq N - 1)
- B_i < B_{i + 1} (1 \leq i \leq N - 1)
- A_i \neq B_j (i \neq j)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 B_1 \vdots A_N B_N
输出
打印答案。
示例输入 1
3 1 3 2 5 4 6
示例输出 1
3
可能的订单是 (1, 2, 3), (2, 1, 3), (1, 3, 2).
示例输入 2
4 1 2 3 4 5 6 7 8
示例输出 2
1
唯一可能的顺序是 (1, 2, 3, 4).