题目描述

ある店を訪れる $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$

输出格式

答えを出力せよ。

题目大意

有 $n$ 个人来过，第 $i$ 个人在 $a_i$ 时刻来在 $b_i$ 时刻走，每个人可以在来时或走时登记，问可能的登记顺序有多少种。

$n\leqslant 5\times 10^5$，$a_i,b_i$ 互不相同，$\forall i<n,a_i<a_{i+1},b_{i}<b_{i+1}$。

translated by cszyf

3
1 3
2 5
4 6

3

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$)
• 入力中の値は全て整数である。

Sample Explanation 1

ありうる順序は $(1,\ 2,\ 3),\ (2,\ 1,\ 3),\ (1,\ 3,\ 2)$ です。

Sample Explanation 2

ありうる順序は $(1,\ 2,\ 3,\ 4)$ のみです。