On vous donne $3n$ points distincts sur un cercle. Chacun de ces points est coloré avec l'une des $n$ couleurs, de telle sorte que chaque couleur apparaisse exactement trois fois.

Vous souhaitez tracer $n$ arcs ne se coupant pas, dont les extrémités sont situées sur les points donnés. Pour ces arcs, les extrémités de chaque arc doivent avoir la même couleur, et aucun autre point sur l'arc ne doit avoir cette couleur.

Notez que vous tracez des arcs, et non des cordes.

Trouvez le nombre de tracés possibles, modulo $998\,244\,353$.

Entrée

La première ligne de l'entrée contient un entier $n$ ($1 \le n \le 200\,000$) : le nombre de couleurs.

La ligne suivante contient $3n$ entiers $c_1, c_2, \dots, c_{3n}$ ($1 \le c_i \le n$) : la couleur du $i$-ième point sur le cercle, dans le sens des aiguilles d'une montre.

Il est garanti que chaque couleur apparaît exactement trois fois.

Sortie

Affichez un entier : le nombre de tracés possibles modulo $998\,244\,353$.

Exemples

Entrée 1

3
1 1 1 2 2 2 3 3 3

Sortie 1

8

Entrée 2

2
1 1 2 2 1 2

Sortie 2

3