ルルは2003年7月23日、メイプルワールドのビクトリアアイランドにある「ヘネシス」と「カニングシティ」の間に位置する「ニウンの森」という名の森で生まれた。当時のニウンの森は未開拓地であり、強力な野生のモンキーであるルパンが生息していたため、自然景観を楽しむために歩き回る一部の冒険者以外は訪れない荒れ地であった。しかし、ルルの家族はニウンの森のロマンチックな景観とともに、愛情を込めてルルを育てた。

やがてルルが成長し小学校に入学する頃、ニウンの森はビクトリアアイランドの再開発事業により、跡形もなく廃墟となった。ルルの家族は積極的に抵抗したが、当時のメイプルワールドの黒幕である暗黒の魔法使いが軍団長を派遣して武力で押し切ったため、やむを得ずカニングシティへ移住することになった。

その出来事はルルにとってトラウマとして残り、ルルは後に無分別な開発によってメイプルワールドが損なわれても、かつてのメイプルワールドの美しさを伝えられるよう、メイプルワールドの多様な風景を題材にした芸術作品を作ることを決意した。ルルはオシアリア大陸、エデルシュタイン、グランディス、時間の神殿、アルカナなど、多様な地域を旅しながら冒険者たちに各地域の風景を描いた絵を贈り、やがて立派なスターアーティストとなった。

もうすぐ二十歳の誕生日を迎えるルルは、誕生日に合わせて特別展を開くことにした。ルルが特別展で最も力を入れて制作する造形物は、かつてのニウンの森の「ㄴ」字地形をモチーフにした「ニウンユニバース」である。ルルは1から $N$ までの異なるサイズを持つ「ㄴ」字型のピースを $N$ 個用意し、各ピースにメイプルワールドの村を一つずつ表現した造形芸術を施した。サイズが $i$ であるピースは、サイズが1の正方形 $2i-1$ 個が横 $i$、縦 $i$ の長さに繋がった形をしており、$C_i$ 番の村を表現している。

ルルは $N$ 個のピースを隙間なく貼り合わせて、横 $N$、縦 $N$ の正方形の造形物を作ろうとしている。各ピースは自由に回転させることができるが、同じ村を表現したピース同士が隣接していると芸術性を損なうため、そのようなピース同士は線分を共有してはならない。

図 A.1: 4つのピースで造形物を正しく作った例

図 A.2: 同じ村を表現するピースが隣接しており正しくない例

ルルは作ることができる造形物の候補をすべて求めた後、その中から最も調和が取れているものを選んで実際の造形物として制作しようとしている。ルルが用意したピースの情報が与えられたとき、作ることができる異なる造形物の総数を求めよ。ただし、回転させて一致させることができる2つの造形物は同じものとみなす。

入力

最初の行にピースの数 $N$ が与えられる。 ($2 \le N \le 3\,000$)

2行目に $N$ 個の整数が空白区切りで与えられる。 $i$ 番目の数は、サイズが $i$ であるピースが表現する村の番号 $C_i$ である。 ($1 \le C_i \le 3\,000$)

出力

作ることができる造形物の総数を $998\,244\,353$ ($= 119 \times 2^{23} + 1$) で割った余りを出力せよ。 $998\,244\,353$ は素数である。

入出力例

入力 1

4
1 2 3 1

出力 1

9