Cube Filling Words

In this problem, you are given an integer $a$ (with $a\ge2$) and a list of $n$ valid words, each of length $a$. You are asked to construct a cube of side length $a$, which is composed of $a^3$ unit cubes. Then, remove all unit cubes that do not lie on an edge of the cube. (Recall that a cube has 12 edges; the only remaining unit cubes are those that lie exactly on these edges; note that the corner cubes are shared by three edges.)

After the removal, each remaining unit cube is filled with a letter. For each of the 12 edges of the cube, when you read off the letters along the edge in one of the two possible directions, you must obtain one of the given valid words. (It is enough that one direction yields a valid word.)

More formally, consider the 8 corner unit cubes as vertices of a cube and the 12 edges connecting them. For each edge connecting vertices $u$ and $v$, assign an ordered word $w = w_1w_2\cdots w_a$ (which is either one of the words in the input or its reverse) so that the letter in the unit cube at $u$ (one endpoint) is $w_1$ and at $v$ is $w_a$. Note that different edges share the corner cubes; hence, the letter assigned to a corner must be consistent with all edges incident to that vertex.

Let $f(x,y)$ be the number of ways a word (or its reverse) in the given list can have its first letter equal to the letter corresponding to $x$ and its last letter equal to the letter corresponding to $y$. Then the answer is the sum over all assignments of letters to the 4 even (or one part of the bipartition) vertices of the cube of the product

$$\prod_{\text{odd vertex } v} \Bigl(\sum_{x=0}^{25} \prod_{u\in N(v)} f(\ell(u), x)\Bigr), $$

where $N(v)$ is the set of its 3 neighbors and $\ell(u)$ is the letter assigned to vertex $u$. Two cubes differing by any rotation or reflection are considered different.

Your task is to compute the number of distinct cubes modulo $998244353$.

inputFormat

The first line contains two integers $a$ and $n$, where $a$ is the side length of the cube and $n$ is the number of valid words. Each of the following $n$ lines contains a word of length $a$. It is guaranteed that $a \ge 2$ and that all words consist of uppercase English letters.

outputFormat

Output a single integer – the number of distinct cubes (i.e. valid letter assignments on the edges) modulo $998244353$.

sample

2 1
AA

1