Lulu 出生於 2003 年 7 月 23 日，地點位於楓之谷維多利亞島上，「赫尼希斯」與「墮落城市」之間的「尼恩森林」。當時的尼恩森林是一片未開發的荒地，且棲息著強大的野生怪物「路殺」，除了少數為了欣賞自然景觀而四處遊蕩的冒險家外，幾乎無人造訪。然而，Lulu 的家人在尼恩森林浪漫的景觀中，傾注了全部心血將 Lulu 撫養長大。

隨著 Lulu 長大並即將進入小學，尼恩森林因維多利亞島的再開發計畫而化為廢墟，連一點痕跡都沒留下。儘管 Lulu 的家人積極抵抗，但當時楓之谷的總統「黑魔法師」派遣了軍團長以武力強行推動，他們最終被迫搬遷至墮落城市。

那次事件在 Lulu 心中留下了創傷。Lulu 後來下定決心，即使楓之谷因無節制的開發而遭到破壞，也要透過藝術作品傳達過去楓之谷的美麗。Lulu 遊歷了奧西里亞大陸、艾德爾斯坦、格蘭蒂斯、時間神殿、奧術之河等各地，為冒險家們繪製了各地的風景畫，最終成為了一名出色的明星藝術家。

即將迎來二十歲生日的 Lulu，決定在生日當天舉辦特別展。Lulu 在特別展中最費心製作的雕塑，是以過去尼恩森林的「ㄴ」字地形為靈感來源的「尼恩宇宙」。Lulu 準備了 $N$ 個大小各異的「ㄴ」字形碎片，每個碎片都融入了表現楓之谷某個村莊的造型藝術。大小為 $i$ 的碎片是由 $2i-1$ 個大小為 1 的正方形，以寬 $i$、高 $i$ 的方式拼貼而成，並代表編號為 $C_i$ 的村莊。

Lulu 想要將這 $N$ 個碎片無縫隙地拼貼在一起，製作成一個寬 $N$、高 $N$ 的正方形雕塑。每個碎片都可以自由旋轉，但由於表現相同村莊的碎片若相鄰會破壞藝術感，因此這些碎片不得共享邊線。

圖 A.1：由 4 個碎片正確組成的雕塑範例

圖 A.2：表現相同村莊的碎片相鄰，導致不正確的範例

Lulu 在找出所有可行的雕塑候選後，打算從中挑選看起來最和諧的一個來製作成實際雕塑。給定 Lulu 準備的碎片資訊，請計算出可以製作出的不同雕塑數量。注意，若兩個雕塑可以透過旋轉使其相同，則視為同一個雕塑。

輸入格式

第一行給定碎片的數量 $N$。($2 \le N \le 3\,000$)

第二行給定 $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