立方体字词是一种特殊类型的填字游戏。构建立方体字时,首先选择一个正整数 $$$a$$$:立方体的边长。然后,你构建一个由 $$$a \times a \times a$$$ 单位立方体组成的大立方体。这个大立方体有 12 条边。然后,丢弃所有不接触大立方体边缘的单位立方体。下图显示了您将通过 $$$a=6$$$ 获得的对象。
最后,为对象中的每个单位立方体分配一个字母。你必须沿着大立方体的每条边得到一个有意义的单词。每个边缘可以在任一方向上读取,并且如果两个读取方向之一给出有意义的单词就足够了。
下图显示了 $$$a=6$$$ 的对象,其中一些单位立方体已经分配了字母。您已经可以沿着大立方体的三个边缘读取“提交”、“接受”和“图灵”一词。
您将获得一个有效单词列表。单词列表中的每个单词都可以出现在有效立方体字的任意多个边上。查找并报告可以构造的不同立方体字的数量,以 $$$998,244,353$$$ 为模。
如果一个立方体字可以通过旋转或镜像从另一个立方体字获得,则它们被认为是不同的。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 100,000$$$) – 单词数。
然后是 $$$n$$$ 行。每一行都包含一个可以出现在大立方体边缘的单词。每个单词的长度在 3 到 10 之间(含 3 和 10)。
保证所有单词都不同。
输出
输出一个整数,即给定有效单词列表的不同立方体单词的数量以 $$$998,244,353$$$ 为模。
示例
输入 #1
1 radar
输出 #1
1
输入 #2
1 robot
输出 #2
2
输入 #3
2 FLOW WOLF
输出 #3
2
输入#4
2 baobab bob
输出#4
4097
输入 #5
3 TURING SUBMIT ACCEPT
输出 #5
162
输入 #6
3 MAN1LA MAN6OS AN4NAS
输出 #6
114
注意
评分:
子任务 1(21 分):单词仅由字母“a”-“f”(小写)组成
子任务2(29分):单词仅由字母'a' - 'p'(小写)组成
子任务3(34分):单词由字母“a”-“p”(小写)和“A”-“P”(大写)组成
子任务4(16分):单词由字母“a”-“z”(小写)、“A”-“Z”(大写)和数字“0”-“9”组成
在第一个示例中,唯一的可能性是单词“radar”出现在立方体的每个边缘上。
在第二个示例中,有两个立方体,它们只是彼此旋转 - 每个边上都有“robot”一词,两个立方体之间的区别在于左下角是否包含“r”或“t”。
第三个示例与第二个示例类似。我们可以从两个方向读取每个边缘上的单词这一事实并不影响答案。
在第四个示例中,有一个立方体的每条边上都有单词“bob”。还有 $$$2^{12} = 4096$$$ 立方体,每条边上都带有单词“baobab”。 (对于 12 条边中的每一条,我们都有两个可能的方向来出现单词“baobab”。)