配点 : $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$

出力

答えを出力せよ。

3
1 3
2 5
4 6

3

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

4
1 2
3 4
5 6
7 8

1

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