CF1570H Chainword

链式填字游戏是一种特殊类型的填字游戏。与大多数填字游戏一样，它有用于填写字母的格子，并且有一些提示来指明这些字母应该是什么。 链式填字游戏的字母格子排成一行。在本题中，我们考虑长度为 $m$ 的链式填字游戏。 链式填字游戏的一个提示是一组分段，这些分段互不重叠且覆盖所有 $m$ 个字母格。每个分段都描述了对应格子中的单词。 不同之处在于，这里实际上有两个提示：一个提示序列在字母格的上方，另一个提示序列在字母格的下方。当这两个序列不同时，它们可以用来消除答案的不确定性。 你将获得一个包含 $n$ 个单词的字典，每个单词由小写拉丁字母组成，所有单词两两不同。 链式填字游戏的一个实例由以下三元组组成： - 一个长度为 $m$ 的小写拉丁字母字符串； - 第一个提示：一组分段，使得每个分段对应的字母拼成字典中的一个单词； - 第二个提示：另一组分段，使得每个分段对应的字母拼成字典中的一个单词。 注意，两组分段序列不一定要不同。 如果两个链式填字游戏实例的字符串、第一组提示或第二组提示不同，则认为它们是不同的。 请计算不同链式填字游戏实例的数量。由于答案可能很大，请输出对 $998\,244\,353$ 取模后的结果。

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 8$，$1 \le m \le 10^9$），表示字典中单词的数量和字母格的数量。 接下来的 $n$ 行，每行包含一个单词——一个非空且长度不超过 $5$ 的小写拉丁字母字符串。所有单词两两不同。

输出一个整数，表示长度为 $m$ 的链式填字游戏的不同实例数量，对 $998\,244\,353$ 取模。

以下是第一个样例中所有合法链式填字游戏实例的示意图：  红色线条表示上方的分段，蓝色线条表示下方的分段。 在第二个样例中，可能的字符串有："abab"、"abcd"、"cdab" 和 "cdcd"。所有提示都是覆盖前两个字母和后两个字母的分段。 由 ChatGPT 4.1 翻译