시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 4 4 4 100.000%

문제

You are given $3n$ different points on a circle. Each of these points is colored in one of $n$ colors, such that each color appears exactly three times. 

You want to draw $n$ non-intersecting arcs with ends on given points. 

For these arcs, the ends of the arc should have equal colors, and no other point on the arc should have this color.

Note that you are drawing arcs, not chords.

Find the number of suitable drawings, modulo $998\,244\,353$.

입력

The first line of input contains one integer $n$ ($1 \leq n \leq 200\,000$): the number of colors.

Next line contains $3n$ integers $c_1, c_2, \ldots, c_{3n}$ ($1 \leq c_i \leq n$): the color of the $i$-th point on the circle, in clockwise order.

It is guaranteed that each color appears exactly three times.

출력

Print one integer: the number of suitable drawings modulo $998\,244\,353$.

예제 입력 1

3
1 1 1 2 2 2 3 3 3

예제 출력 1

8

예제 입력 2

2
1 1 2 2 1 2

예제 출력 2

3