CF1192C.Cubeword

A cubeword is a special type of a crossword. When building a cubeword, you start by choosing a positive integer $a$: the side length of the cube. Then, you build a big cube consisting of $a \times a \times a$ unit cubes. This big cube has 12 edges. Then, you discard all unit cubes that do not touch the edges of the big cube. The figure below shows the object you will get for $a=6$.

Finally, you assign a letter to each of the unit cubes in the object. You must get a meaningful word along each edge of the big cube. Each edge can be read in either direction, and it is sufficient if one of the two directions of reading gives a meaningful word.

The figure below shows the object for $a=6$ in which some unit cubes already have assigned letters. You can already read the words 'SUBMIT', 'ACCEPT' and 'TURING' along three edges of the big cube.

You are given a list of valid words. Each word from the wordlist may appear on arbitrarily many edges of a valid cubeword. Find and report the number of different cubewords that can be constructed, modulo $998,244,353$.

If one cubeword can be obtained from another by rotation or mirroring, they are considered distinct.

“立方字谜”（cubeword）是一种特殊的填字游戏。构造一个立方字谜时，你首先选择一个正整数 $a$：即大立方体的边长。接着，你构建一个由 $a \times a \times a$ 个单位立方体组成的大立方体。该大立方体共有 12 条棱。然后，你丢弃所有不与大立方体棱相接触的单位立方体。下图展示了当 $a=6$ 时所得的立体结构。

最后，你为该结构中每个剩余的单位立方体分配一个字母。要求：沿大立方体的每一条棱，所经过的单位立方体上的字母按顺序拼成一个有意义的单词。每条棱可从任一方向阅读（即正向或反向），只要其中一个方向能构成有效单词即可。

下图展示了 $a=6$ 时的结构，其中部分单位立方体已预先填入字母。此时，你已可在大立方体的三条棱上分别读出单词 'SUBMIT'、'ACCEPT' 和 'TURING'。

你将获得一个有效单词列表。在合法的立方字谜中，单词表中的每个单词可以出现在任意多条棱上（允许重复使用）。请计算并报告可构造的不同立方字谜的总数，结果对 $998\,244\,353$ 取模。

若一个立方字谜可通过旋转或镜像变换得到另一个，则二者视为不同的立方字谜。

The first line contains a single integer $n$ ($1 \leq n \leq 100,000$) – the number of words.

Then, $n$ lines follow. Each of these lines contains one word that can appear on the edges of the big cube. The length of each word is between 3 and 10, inclusive.

It is guaranteed that all words are different.

第一行包含一个整数 $n$（$1 \leq n \leq 100{,}000$）——表示单词的个数。

接下来有 $n$ 行，每行包含一个单词，该单词可能出现在大立方体的棱上。每个单词的长度在 $3$ 到 $10$ 之间（含端点）。

保证所有单词互不相同。

Output a single integer, the number of distinct cubewords for the given list of valid words modulo $998,244,353$.

输出一个整数，表示给定有效单词列表中不同立方词（cubewords）的数量对 $998,244,353$ 取模的结果。

In the first sample, the only possibility is for the word "radar" to be on each edge of the cube.

In the second sample, there are two cubes, which are just rotations of each other – the word "robot" is on every edge, and the difference between the two cubes is whether the lower left front corner contains 'r' or 't'.

The third sample is similar to the second one. The fact that we can read the word on each edge in both directions does not affect the answer.

In the fourth sample, there is one cube with the word "bob" on each edge. There are also $2^{12} = 4096$ cubes with the word "baobab" on each edge. (For each of the 12 edges, we have two possible directions in which the word "baobab" can appear.)

在第一个样例中，唯一可能的情况是立方体的每条边上都是单词 “radar”。

在第二个样例中，存在两个立方体，它们彼此仅为旋转关系——每条边上均为单词 “robot”，这两个立方体的差别仅在于左下前角处放置的是字母 ‘r’ 还是 ‘t’。

第三个样例与第二个类似。由于我们可以在每条边上双向读取该单词，这一事实并不影响答案。

在第四个样例中，存在一个每条边上均为单词 “bob” 的立方体；此外，还有 $2^{12} = 4096$ 个每条边上均为单词 “baobab” 的立方体。（对于 12 条边中的每一条，单词 “baobab” 均有两种可能的书写方向。）