To experience the human condition, the Sun God descended to earth under the pseudonym {errors occur in processing :user}. [EntropyIncreaser], or EI for short, is written as "日" (Sun), signifying the Sun God.

Today, {errors occur in processing :user} gathered $n$ members from his fan group to participate in his banquet. At the banquet, he played puzzle games with the members to demonstrate his boundless wisdom.

One side of the game is {errors occur in processing :user}; the other side consists of $n$ members, who stand in a line and are numbered $1, 2, \ldots, n$ in order. The character set is the set of the first $k$ English letters, $\Sigma$; that is, all strings in the game are composed of elements from $\Sigma$.

At the beginning of the game, {errors occur in processing :user} gave each member a string, where the $i$-th member's string is $S_i$. Subsequently, each member arbitrarily chooses a substring $T_i$ from the received string $S_i$ (the substring must be contiguous, but can be empty). The members input their chosen substrings $T_i$ into a typewriter, and they are concatenated in order without gaps to form a complete string $T = T_1T_2\cdots T_n$. {errors occur in processing :user} only knows $T$ and does not know which member input which character. The rule of the game is that as long as a set of possible $T_1, T_2, \ldots, T_n$ can be solved, one wins.

{errors occur in processing :user} saw the string $T$ and, without hesitation, partitioned it into $n$ strings $T'_1T'_2\cdots T'_n$ (which can also be empty). The members were surprised to find that $T'_i$ was indeed a substring of the string $S_i$ they had received!

{errors occur in processing :user} smiled: "This is a very simple problem, nothing difficult. Let's increase the difficulty a little bit."

At this point, the Moon Goddess Ling Yu proposed an enhanced version of the game.

Now, the $i$-th member still picks out a substring $T_i$. Before each member inputs, the keyboard layout is secretly shuffled, but the members still input as usual. That is, each member is now assigned a permutation $f_i$ on $\Sigma$. When the $j$-th character $T_{ij}$ of $T_i$ is input, it becomes $f_i(T_{ij})$, and all input characters are concatenated to form $T$. {errors occur in processing :user}'s goal is still to solve for a set of possible $T_1, T_2, \ldots, T_n$.

{errors occur in processing :user} examined it carefully and again split $T$ into $n$ strings $T'_1, T'_2, \ldots, T'_n$. The members were in an uproar: there indeed exist permutations $f_i$ such that a substring of $S_i$ transformed by $f_i$ results in $T'_i$!

The banquet lasted from dawn until night. At the end of the banquet, {errors occur in processing :user} announced: "The God will bestow mathematical wisdom upon the group members, but they must first pass three trials."

Now, the first trial from the Great Enhancement of the God of Counting is placed before you—please count how many strings $T$ have at least one solution in the last game. The answer may be very large, so output it modulo $998244353$.

Input

The first line contains two positive integers $n, k$.

The next $n$ lines each contain a string, representing $S_1, S_2, \ldots, S_n$ in order.

Output

Output the number of strings that have a solution, modulo $998244353$.

Examples

Input 1

2 2
aa
a

Output 1

11

Note 1

Let $\epsilon$ denote the empty string.

The substrings of $S_1$ are $\epsilon$, a, aa. After shuffling the keys, one can obtain $\epsilon$, a, b, aa, bb.

The substrings of $S_2$ are $\epsilon$, a. After shuffling the keys, one can obtain $\epsilon$, a, b.

Concatenating them, the strings with solutions are: $\epsilon$, a, b, aa, ab, ba, bb, aaa, aab, bba, bbb.

Input 2

2 2
aa
ab

Output 2

17

Constraints

Let $L = \sum_{i=1}^n |S_i|$.

It is guaranteed that $2 \le k \le 26$, $S_i$ is non-empty, and $L \le 10^6$.

Subtask 1 (2 points): $n=1$, $k=2$, $L \le 1000$.

Subtask 2 (7 points): $n=1$, $L \le 1000$.

Subtask 3 (11 points): $n=1$, $L \le 10^5$.

Subtask 4 (13 points): $k=2$, $L \le 1000$.

Subtask 5 (17 points): $L \le 1000$.

Subtask 6 (31 points): $k \le 5$.

Subtask 7 (19 points): No special constraints.