A. 圆弧（arc）

一个圆上有 $3n$ 个不同的点，每个点都被染成了 $n$ 种颜色中的一种。每种颜色恰好出现了 $3$ 次。

你想对每种颜色 $c$ 画一条圆弧，满足其两端点的颜色都是 $c$ 且不经过另一个颜色为 $c$ 的点。要求这 $n$ 条圆弧互不相交。

求画圆弧的方案数对 $998244353$ 取模后的结果。

输入格式

第一行一个整数 $n$（$1\le n\le 200000$），表示颜色的数量。

第二行 $3n$ 个整数 $c_1,c_2,\ldots,c_{3n}$（$1\le c_i\le n$），$c_i$ 表示圆上按逆时针顺序第 $i$ 个点的颜色。

保证每种颜色恰好出现 $3$ 次。

输出格式

一个整数，表示方案数对 $998244353$ 取模后的结果。

样例

样例输入 1

3
1 1 1 2 2 2 3 3 3

样例输出 1

8

样例输入 2

2
1 1 2 2 1 2

样例输出 2

3

样例输入 3

见下发文件中的 arc/ex_arc3.in。

样例输出 3

472188790

子任务

• Subtask 1（10 points）： $n\le 14$。
• Subtask 2（20 points）： $n\le 300$。
• Subtask 3（10 points）： $n\le 5000$。
• Subtask 4（60 points）： 无额外限制。