#P18297. Elegia❄️'s Mind

Elegia❄️'s Mind

Elegia❄️'s Mind

有 nn 个完全相同的立方体,每个立方体的六个面分别涂有六种不同的颜色,颜色编号为 00 至 55。

所有立方体在三维空间中旋转后都可以得到相同的朝向:前、上、右、左、下、后六个面的颜色依次为 0,1,2,3,4,50,1,2,3,4,5。因此,颜色 cc 的对面颜色总是 5−c5-c。只允许旋转,不允许镜像反射。

将所有立方体从左到右排成一行。按照立方体在这一行中的顺序,分别记录它们前、上、右、左、下、后六个方向上的面颜色,便得到六条长度为 nn 的颜色序列。

给定一个允许序列的集合,求有多少种立方体朝向安排,使上述六条颜色序列全部属于允许集合。答案对 998244353998244353 取模。

立方体完全相同,所以不区分“哪一个立方体放在哪一个位置”。每个位置只有朝向的区别。一个立方体有 2424 种旋转朝向,因此不考虑允许集合限制时,一共有 24n24^n 种安排。

允许集合用一个长度为 6n6^n 的字符串 ss 表示,字符均为 0 或 1。对于从左到右的颜色序列

a0,a1,…,an−1,a_0,a_1,\ldots,a_{n-1},

定义其编号为

k=∑i=0n−1ai6i.k=\sum_{i=0}^{n-1}a_i6^i.

当且仅当 ss 中下标为 kk 的字符为 1 时,这条序列被允许。字符串下标从 00 开始;最左边立方体的颜色对应六进制编号的最低位。

输入格式

第一行包含一个整数 nn,满足 1≤n≤91\le n\le9。

第二行包含恰好 6n6^n 个字符 0 或 1,表示字符串 ss。

本题只有一组输入,没有测试组数 TT。

输出格式

输出一个整数,表示合法安排的数量对 998244353998244353 取模的结果。

样例 1

1
111111
24

样例 2

1
110111
0

样例 3

2
000001001000010000000010000100100000
24

样例 4

2
111111111111111111111111111111111111
576