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