CF1511F.Chainword

A chainword is a special type of crossword. As most of the crosswords do, it has cells that you put the letters in and some sort of hints to what these letters should be.

The letter cells in a chainword are put in a single row. We will consider chainwords of length $m$ in this task.

A hint to a chainword is a sequence of segments such that the segments don't intersect with each other and cover all $m$ letter cells. Each segment contains a description of the word in the corresponding cells.

The twist is that there are actually two hints: one sequence is the row above the letter cells and the other sequence is the row below the letter cells. When the sequences are different, they provide a way to resolve the ambiguity in the answers.

You are provided with a dictionary of $n$ words, each word consists of lowercase Latin letters. All words are pairwise distinct.

An instance of a chainword is the following triple:

• a string of $m$ lowercase Latin letters;
• the first hint: a sequence of segments such that the letters that correspond to each segment spell a word from the dictionary;
• the second hint: another sequence of segments such that the letters that correspond to each segment spell a word from the dictionary.

Note that the sequences of segments don't necessarily have to be distinct.

Two instances of chainwords are considered different if they have different strings, different first hints or different second hints.

Count the number of different instances of chainwords. Since the number might be pretty large, output it modulo $998\,244\,353$.

链词（chainword）是一种特殊的填字游戏。与大多数填字游戏一样，它包含若干用于填写字母的单元格，以及若干提示信息，用以指示这些单元格中应填入的字母。

链词中的字母单元格排布成单行。本题中我们仅考虑长度为 $m$ 的链词。

链词的提示信息是一组互不相交且完全覆盖全部 $m$ 个字母单元格的区间序列；每个区间对应一个单词描述，该描述指明了该区间所覆盖单元格中应填入的单词。

特别之处在于：实际上存在两组提示信息——一组位于字母单元格所在行的上方，另一组位于其下方。当这两组提示信息不同时，便能消除答案的歧义。

你将获得一个包含 $n$ 个单词的词典，每个单词均由小写拉丁字母组成，且所有单词两两互异。

一个链词实例定义为如下三元组：

• 一个长度为 $m$ 的、由小写拉丁字母组成的字符串；
• 第一组提示（上方提示）：一组区间序列，使得每个区间所覆盖的字母恰好拼出词典中的某个单词；
• 第二组提示（下方提示）：另一组区间序列，使得每个区间所覆盖的字母也恰好拼出词典中的某个单词。

注意：两组区间序列不一定互不相同。

若两个链词实例的字符串不同，或第一组提示不同，或第二组提示不同，则认为它们是不同的实例。

请计算不同的链词实例总数。由于结果可能非常大，请对 $998\,244\,353$ 取模后输出。

The first line contains two integers $n$ and $m$ ($1 \le n \le 8$, $1 \le m \le 10^9$) — the number of words in the dictionary and the number of letter cells.

Each of the next $n$ lines contains a word — a non-empty string of no more than $5$ lowercase Latin letters. All words are pairwise distinct.

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 8$，$1 \le m \le 10^9$）—— 分别表示字典中单词的数量和字母格子的数量。

接下来的 $n$ 行每行包含一个单词 —— 一个非空字符串，由至多 $5$ 个小写拉丁字母组成。所有单词两两互不相同。

Print a single integer — the number of different instances of chainwords of length $m$ for the given dictionary modulo $998\,244\,353$.

输出一个整数——对于给定字典，长度为 $m$ 的不同链词（chainword）的数量，对 $998\,244\,353$ 取模。

Here are all the instances of the valid chainwords for the first example:

The red lines above the letters denote the segments of the first hint, the blue lines below the letters denote the segments of the second hint.

In the second example the possible strings are: "abab", "abcd", "cdab" and "cdcd". All the hints are segments that cover the first two letters and the last two letters.

以下是第一个示例中所有合法链词（chainwords）的实例：

字母上方的红色线段表示第一条提示所覆盖的子串，字母下方的蓝色线段表示第二条提示所覆盖的子串。

在第二个示例中，可能的字符串有："abab"、"abcd"、"cdab" 和 "cdcd"。所有提示均为覆盖前两个字母和后两个字母的子串。