题目描述

露露于 2003 年 7 月 23 日出生在冒险岛世界维多利亚岛上，位于“射手村”和“废弃都市”之间的一片名为“尼恩森林”的森林中。当时的尼恩森林尚未开发，且栖息着强大的野生猴子露邦。除了少数为了欣赏自然风景而四处游历的冒险家之外，几乎无人到访。尽管如此，露露的家人仍在尼恩森林浪漫的景色中悉心将她抚养长大。

当露露长大到即将进入小学时，尼恩森林因维多利亚岛再开发工程而被彻底夷为废墟。露露的家人积极反抗，但当时冒险岛世界的总统黑魔法师派遣军团长，以武力强行推进开发，他们最终只能搬往废弃都市。

这件事给露露留下了心理创伤。她决定，即使未来冒险岛世界因无节制的开发而遭到破坏，也要通过艺术作品，将昔日冒险岛世界的美丽传递下去。露露游历了奥西利亚大陆、埃德尔斯坦、格兰蒂斯、时间神殿、奥术之河等众多地区，为冒险家们绘制当地风景，最终成长为一位知名艺术家。

即将迎来二十岁生日的露露，决定举办一场特别展览。她最用心准备的雕塑作品名为“尼恩宇宙”，灵感来自昔日尼恩森林的 ㄴ 形地貌。

露露准备了 $N$ 块大小互不相同的 ㄴ 形拼块，大小依次为 $1,2,\ldots,N$。每块拼块上都表现了冒险岛世界中的一个村庄。

大小为 $i$ 的拼块由 $2i-1$ 个边长为 $1$ 的正方形组成，其横向长度和纵向长度均为 $i$，并表现编号为 $C_i$ 的村庄。

大小为 1 至 4 的拼块

露露想把这 $N$ 块拼块无缝拼接成一个边长为 $N$ 的正方形。每块拼块都可以自由旋转。

如果表现同一个村庄的两块拼块彼此相邻，会破坏作品的艺术性。因此，表现同一个村庄的任意两块拼块都不能共享一条具有正长度的线段。

图 A.1：使用 4 块拼块正确构成作品的示例。

图 A.2：表现同一村庄的拼块共享边界，因此不合法。

露露想先找出所有可以制作的作品，再从中挑选最协调的一件实际制作。

给定每块拼块的信息，求可以构成多少种不同的作品。

两件作品如果可以通过旋转整个作品而完全重合，则认为它们是同一种作品。

输入格式

第一行包含一个整数 $N$，表示拼块数量。

第二行包含 $N$ 个整数 $C_1,C_2,\ldots,C_N$。其中 $C_i$ 表示大小为 $i$ 的拼块所表现的村庄编号。

输出格式

输出可以构成的不同作品数量对 $998244353$ 取模后的结果。

$998244353=119\times 2^{23}+1$，且它是一个质数。

样例

输入

4
1 2 3 1

输出

9