AT_agc061_c [AGC061C] First Come First Serve

题目描述

有 $N$ 位顾客会光顾某家店，我们将他们编号为 $1,\ldots,N$。第 $i$ 位顾客在时刻 $A_i$ 进入店内，在时刻 $B_i$ 离开店铺。该店的排队方式为“先进先出”，并且 $A_i$ 和 $B_i$ 都是严格递增的。此外，所有的 $A_i$ 和 $B_i$ 互不相同。

在店门口有一份顾客可以签名的名单。每位顾客仅能在入店时或离店时，将自己的名字写在名单的末尾一次。请问，最终名单上名字的可能排列方式有多少种？请将答案对 $998\,244\,353$ 取模后输出。

输入格式

输入从标准输入读入，格式如下：

$N$
$A_1$ $B_1$
$\vdots$
$A_N$ $B_N$

输出格式

请输出答案。

样例 1

输入

3
1 3
2 5
4 6

输出

3

样例 2

输入

4
1 2
3 4
5 6
7 8

输出

1

说明/提示

限制条件

• $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$）
• 输入中的所有值均为整数。

样例解释 1

可能的排列有 $(1,\ 2,\ 3),\ (2,\ 1,\ 3),\ (1,\ 3,\ 2)$。

样例解释 2

可能的排列仅有 $(1,\ 2,\ 3,\ 4)$。

由 ChatGPT 4.1 翻译