Lulu est née le 23 juillet 2003 dans la « Forêt de Nieun », située entre les villages de « Henesys » et « Kerning City » sur l'île de Victoria dans Maple World. À l'époque, la forêt de Nieun était une terre sauvage et inexplorée, habitée par de puissants singes sauvages appelés Lupins, et n'était visitée que par quelques aventuriers en quête de paysages naturels. Cependant, la famille de Lulu a élevé Lulu avec beaucoup de soin, entourée par le paysage romantique de la forêt.

Alors que Lulu grandissait et s'apprêtait à entrer à l'école primaire, la forêt de Nieun a été dévastée et a disparu sans laisser de traces à cause d'un projet de réaménagement de l'île de Victoria. Bien que la famille de Lulu ait résisté activement, elle a été contrainte de déménager à Kerning City lorsque le président de Maple World de l'époque, le Mage Noir, a envoyé ses commandants pour imposer le projet par la force.

Cet événement a laissé un traumatisme à Lulu, qui a décidé plus tard de créer des œuvres d'art représentant divers paysages de Maple World, afin que la beauté passée de ce monde puisse être transmise même si Maple World venait à être endommagé par un développement inconsidéré. Lulu a voyagé dans diverses régions telles que le continent Ossyria, Edelstein, Grandis, le Temple du Temps et Arcane River, dessinant des paysages pour les aventuriers, et est finalement devenue une artiste renommée.

À l'approche de son vingtième anniversaire, Lulu a décidé d'organiser une exposition spéciale. L'œuvre sur laquelle Lulu a le plus travaillé pour cette exposition est « Nieun Universe », inspirée par la topographie en forme de « ㄴ » (Nieun) de l'ancienne forêt de Nieun. Lulu a préparé $N$ pièces en forme de « ㄴ » de tailles différentes, allant de 1 à $N$, et a intégré dans chaque pièce une œuvre d'art représentant un village de Maple World. Une pièce de taille $i$ est formée par $2i - 1$ carrés de taille 1, assemblés pour former une largeur de $i$ et une hauteur de $i$, et représente le village numéro $C_i$.

Lulu souhaite assembler les $N$ pièces sans aucun espace pour créer une sculpture en forme de carré de largeur $N$ et de hauteur $N$. Chaque pièce peut être tournée librement. Cependant, pour préserver l'esthétique, deux pièces représentant le même village ne doivent pas partager de segment de bordure si elles sont adjacentes.

Figure A.1 : Exemple de sculpture correctement réalisée avec 4 pièces

Figure A.2 : Exemple de sculpture incorrecte où des pièces représentant le même village sont adjacentes

Lulu souhaite trouver tous les candidats possibles pour la sculpture, puis en choisir un qui semble le plus harmonieux pour le réaliser. Étant donné les informations sur les pièces préparées par Lulu, calculez le nombre de sculptures différentes qui peuvent être créées. Notez que deux sculptures qui peuvent être rendues identiques par rotation sont considérées comme une seule et même sculpture.

Entrée

La première ligne contient le nombre de pièces $N$ ($2 \le N \le 3\,000$). La deuxième ligne contient $N$ entiers séparés par des espaces. Le $i$-ième nombre est le numéro du village $C_i$ représenté par la pièce de taille $i$ ($1 \le C_i \le 3\,000$).

Sortie

Affichez le nombre de sculptures possibles modulo $998\,244\,353$ ($= 119 \times 2^{23} + 1$). $998\,244\,353$ est un nombre premier.

Exemples

Entrée 1

4
1 2 3 1

Sortie 1

9