問題文

$2N$ 人の人 ($1$ 番から $2N$ 番まで) がいます。 人 $i$ の身長は $h_i$ です。

以下の条件を満たすように、$N$ 個の人のペアを作る方法は何通りありますか？ 答えを modulo $998,244,353$ で求めてください。

• どの人もちょうど一つのペアに含まれる。
• どのペアも、そのペアに属する二人の人の身長が異なる。

ある $p$ と $q$ に対し、人 $p$ と人 $q$ がペアになったかどうかが異なる場合、異なる方法であるとみなします。

制約

• $1 \\leq N \\leq 50,000$
• $1 \\leq h_i \\leq 100,000$
• 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $h_1$ $:$ $h_{2N}$

出力

答えを出力せよ。

入力例 1

2
1
1
2
3

出力例 1

2

二通りあります:

• ペア (人 $1$, 人 $3$) とペア (人 $2$, 人 $4$) を作る。
• ペア (人 $1$, 人 $4$) とペア (人 $2$, 人 $3$) を作る。

入力例 2

5
30
10
20
40
20
10
10
30
50
60

出力例 2

516