원 위에 $3n$개의 서로 다른 점이 주어집니다. 각 점은 $n$개의 색상 중 하나로 칠해져 있으며, 각 색상은 정확히 세 번씩 나타납니다.

주어진 점들을 양 끝점으로 하는 $n$개의 교차하지 않는 호(arc)를 그리고자 합니다. 각 호의 양 끝점은 같은 색이어야 하며, 호 위의 다른 어떤 점도 그 색을 가져서는 안 됩니다.

현(chord)이 아닌 호를 그리고 있다는 점에 유의하십시오.

적절한 그리기 방법의 수를 $998\,244\,353$으로 나눈 나머지를 구하십시오.

입력

첫 번째 줄에는 색상의 개수를 나타내는 정수 $n$ ($1 \le n \le 200\,000$)이 주어집니다.

다음 줄에는 원 위에 시계 방향 순서로 배치된 $i$번째 점의 색상을 나타내는 $3n$개의 정수 $c_1, c_2, \dots, c_{3n}$ ($1 \le c_i \le n$)이 주어집니다.

각 색상은 정확히 세 번 나타남이 보장됩니다.

출력

적절한 그리기 방법의 수를 $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