니은숲 예술가

루루는 2003년 7월 23일 메이플 월드 빅토리아 아일랜드의 헤네시스와 커닝시티 사이에 있는 니은숲에서 태어났다. 당시 니은숲은 손이 닿지 않은 미개척지였고, 강력한 야생 원숭이 루팡이 살고 있었다. 자연경관을 감상하려는 일부 모험가 말고는 찾는 사람이 거의 없었다. 그래도 루루의 가족은 숲의 낭만적인 풍경에 둘러싸여 루루를 지극정성으로 키웠다.

루루가 초등학교에 입학할 무렵, 빅토리아 아일랜드 재개발 사업으로 니은숲은 흔적도 없이 폐허가 되었다. 루루의 가족은 끝까지 저항했지만, 메이플 월드의 대통령 검은 마법사가 군단장을 보내 무력으로 밀어붙였다. 가족은 어쩔 수 없이 커닝시티로 이주했다.

그 사건은 루루에게 트라우마로 남았다. 루루는 나중에 무분별한 개발로 메이플 월드가 훼손되더라도 과거의 아름다움을 전할 수 있도록, 메이플 월드의 다양한 풍경을 담은 예술 작품을 만들기로 결심했다. 루루는 오시리아 대륙, 에델슈타인, 그란디스, 시간의 신전, 아케인 리버 등을 여행하며 모험가들에게 지역별 풍경을 그려 주었고, 마침내 이름난 스타 예술가가 되었다.

루루는 곧 스무 살 생일을 맞아 생일에 맞춰 특별전을 열기로 했다. 루루가 특별전에서 가장 공들여 만들 조형물은 과거 니은숲의 ㄴ자 지형에서 모티브를 딴 '니은 유니버스'다. 루루는 $1$부터 $N$까지 서로 다른 크기를 가진 ㄴ자 모양 조각 $N$개를 준비하고, 각 조각에 메이플 월드의 마을 하나를 표현한 조형 예술을 담았다. 크기가 $i$인 조각은 가로 $i$, 세로 $i$의 ㄴ자 모양으로 붙은 크기 1인 정사각형 $2i-1$개로 이루어져 있으며, $C_i$번 마을을 표현한다.

루루는 $N$개의 조각을 빈틈없이 붙여 가로 $N$, 세로 $N$인 정사각형 조형물을 만들려고 한다. 각 조각은 자유롭게 회전할 수 있다. 같은 마을을 표현한 조각끼리 선분을 공유하면 예술성을 해치므로 이런 조각들은 변을 맞댈 수 없다.

그림 A.1: 4개의 조각으로 조형물을 올바르게 만든 예시	그림 A.2: 같은 마을을 표현하는 조각이 붙어 있어 올바르지 않은 예시

루루는 만들 수 있는 조형물의 후보를 모두 구한 뒤, 그중 가장 조화롭게 보이는 것을 골라 실제로 제작하려고 한다. 루루가 준비한 조각들의 정보가 주어질 때, 만들 수 있는 서로 다른 조형물의 가짓수를 구하라. 회전시켜서 같게 만들 수 있는 두 조형물은 같은 조형물이다.

첫 번째 줄에 조각의 수 $N$이 주어진다. $(2\leq N\leq 3\, 000)$

두 번째 줄에 $N$개의 정수가 공백으로 구분되어 주어진다. $i$번째 수는 크기가 $i$인 조각이 표현하는 마을 번호 $C_i$이다. $(1\leq C_i\leq 3\, 000)$

만들 수 있는 조형물의 가짓수를 $998\, 244\, 353$ $(=119\times 2^{23}+1)$으로 나눈 나머지를 출력한다. $998\, 244\, 353$은 소수이다.