CF1511F 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 翻译