Joining Points

원 위에 놓인 3n개의 점을 색별로 세 번씩 등장하도록 칠했을 때, 같은 색이면서 그 사이에 같은 색이 없는 두 점을 잇는 교차하지 않는 호를 그리는 방법의 수를 구한다.

어려움8동적 계획법조합론스택아직 제출이 없습니다시간 제한1초메모리 제한512 MB

문제 설명

예제2

문제

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$ .