有 $n$ 个相同的立方体，每个面的颜色被涂成六种不同颜色中的一种。颜色用 $0$ 到 $5$ 的整数编号。所有立方体在三维空间旋转意义下是相同的。具体来说，所有立方体都可以通过旋转使得前表面为颜色 $0$，顶表面为颜色 $1$，右表面为颜色 $2$，左表面为颜色 $3$，底表面为颜色 $4$，后表面为颜色 $5$。

假设我们将所有这些立方体从左到右排成一行。这种排列自然会产生以下六个长度为 $n$ 的颜色序列：从左到右观察时，立方体的前/顶/右/左/底/后表面的颜色。有多少种排列立方体的方法，使得所有这六个序列都在指定的允许序列集合内？

由于立方体是相同的，哪个立方体放在序列的第一位、第二位等并不重要。因此，总共有 $24^n$ 种排列方式：每个立方体有 $24$ 种旋转方式。当然，并非所有可能的排列都满足面颜色的条件。

允许序列的集合由一个显式的 $6^n$ 个字符“0”和“1”组成的字符串给出。颜色序列 $a_0, a_1, \dots, a_{n-1}$（其中每个 $a_i$ 是 $0$ 到 $5$ 之间的整数）是允许的，当且仅当该字符串的第 $\sum_{i=0}^{n-1} (a_i \cdot 6^i)$ 个字符（从 $0$ 开始索引）为“1”。

尽管问题的答案本身并不很大，请输出其对质数 $998\,244\,353$ 取模的结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 9$)，表示立方体的数量。第二行包含一个长度为 $6^n$ 的字符串，由“0”和“1”组成，其中第 $k$ 个字符（从 $0$ 开始索引）为“1”当且仅当 $k$ 的六进制表示作为颜色序列是被允许的。

输出格式

一个整数：问题的答案对 $998\,244\,353$ 取模的结果。

样例

样例输入 1

1
111111

样例输出 1

24

样例输入 2

1
110111

样例输出 2

0

样例输入 3

2
000001001000010000000010000100100000

样例输出 3

24

样例输入 4

2
111111111111111111111111111111111111

样例输出 4

576