链字谜是一种特殊类型的填字游戏。与大多数填字游戏一样,它具有用于放置字母的单元格以及有关这些字母应该是什么的某种提示。
链词中的字母单元放在一行中。我们将在此任务中考虑长度为 $$$m$$$ 的链词。
链词的提示是一系列段,这些段不会彼此相交并覆盖所有 $$$m$$$ 字母单元。每个段都包含相应单元格中单词的描述。
不同的是,实际上有两个提示:一个序列是字母单元上方的行,另一个序列是字母单元下方的行。当序列不同时,它们提供了一种解决答案中歧义的方法。
为您提供了一本包含 $$$n$$$ 个单词的字典,每个单词都由小写拉丁字母组成。所有单词都是成对不同的。
链字词的一个实例是以下三元组:
- $$$m$$$ 小写拉丁字母组成的字符串;
- 第一个提示:一系列片段,每个片段对应的字母可以拼写字典中的一个单词;
- 第二个提示:另一个段序列,使得与每个段对应的字母拼写字典中的单词。
请注意,段的序列不一定必须是不同的。
如果两个链词实例具有不同的字符串、不同的第一提示或不同的第二提示,则它们被视为不同。
计算不同链字实例的数量。由于数字可能相当大,因此输出它对 $$$998\,244\,353$$$ 取模。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 8$$$, $$$1 \le m \le 10^9$$$) — 字典中的单词数和字母单元格数。
接下来的 $$$n$$$ 行都包含一个单词 - 不超过 $$$5$$$ 小写拉丁字母的非空字符串。所有单词都是成对不同的。
输出
打印单个整数 - 给定字典模 $$$998\,244\,353$$$ 的长度为 $$$m$$$ 的链字的不同实例的数量。
示例
输入 #1
3 5 ababa ab a
输出 #1
11
输入 #2
2 4 ab cd
输出 #2
4
输入 #3
5 100 a aa aaa aaaa aaaaa
输出 #3
142528942
注意
以下是第一个示例的有效链字的所有实例:
字母上方的红线表示第一个提示的片段,字母下方的蓝线表示第二个提示的片段。
在第二个示例中,可能的字符串是:“abab”、“abcd”、“cdab”和“cdcd”。所有提示都是涵盖前两个字母和最后两个字母的片段。