円周上に $3n$ 個の異なる点が与えられています。各点は $n$ 色のうちのいずれかで塗られており、各色はちょうど 3 回ずつ現れます。

あなたは、与えられた点を端点とする $n$ 本の交差しない弧を描きたいと考えています。 これらの弧について、弧の両端点は同じ色でなければならず、また弧上の他のどの点もその色であってはなりません。

注意：描くのは弦ではなく弧です。

適切な描き方の総数を $998\,244\,353$ で割った余りを求めてください。

入力

入力の最初の行には、整数 $n$ ($1 \le n \le 200\,000$) が含まれます。これは色の数です。 次の行には、$3n$ 個の整数 $c_1, c_2, \dots, c_{3n}$ ($1 \le c_i \le n$) が含まれます。これは円周上の時計回りの順序における $i$ 番目の点のの色です。

各色がちょうど 3 回ずつ現れることが保証されています。

出力

適切な描き方の総数を $998\,244\,353$ で割った余りを 1 つの整数として出力してください。

入出力例

入力 1

3
1 1 1 2 2 2 3 3 3

出力 1

8

入力 2

2
1 1 2 2 1 2

出力 2

3