Joining Points

Time limit1sMemory limit512 MB

Summary

Count the sets of n non-crossing arcs on a circle, each joining two same-colored points with no point of that color inside the arc.

Level: Hard8 of 10
Topics: Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

You are given $3n$ different points on a circle. Each point is colored with one of $n$ colors, and each color appears exactly three times.

You want to draw $n$ non-intersecting arcs, with ends on the given points. For each arc, the two ends have the same color, and no other point on that arc has this color.

Note that you are drawing arcs, not chords.

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

Input

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

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

Output

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

Examples2

Example 1
Input
```
3
1 1 1 2 2 2 3 3 3
```
Expected output
```
8
```
Example 2
Input
```
2
1 1 2 2 1 2
```
Expected output
```
3
```