시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)2461065041.322%

문제

루루는 2003년 7월 23일 메이플 월드 빅토리아 아일랜드의 두 마을 “헤네시스”와 “커닝시티” 사이에 있는 “니은숲”이라는 이름의 숲에서 태어났다. 당시 니은숲은 미개척지인데다가 강력한 야생 원숭이 루팡이 서식하고 있어서, 자연경관을 감상하기 위해서 돌아다니는 일부 모험가 외에는 오지 않던 척박한 땅이었다. 그러나 루루의 가족은 니은숲의 낭만적인 경관과 함께 지극정성으로 루루를 키웠다.

어느덧 루루가 자라 초등학교에 입학하게 될 무렵, 니은숲은 빅토리아 아일랜드 재개발 사업으로 인해 흔적도 남기지 않고 폐허가 되었다. 루루의 가족은 적극적으로 저항했지만, 당시 메이플 월드의 대통령 검은 마법사가 군단장을 파견하여 무력으로 밀어붙이자 어쩔 수 없이 커닝시티로 이주하게 되었다.

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

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

예제 입력 1

4
1 2 3 1

예제 출력 1

9