Чайнворд — это особый тип кроссворда. Как и в большинстве кроссвордов, в нем есть клетки, в которые надо вписать буквы, и некоторые подсказки, которые указывают на то, какие буквы должны быть.
В чайнворде клетки для букв расположены в одну строку. В этой задаче мы будем рассматривать чайнворды длины $$$m$$$.
Подсказка к чайнворду — это последовательность отрезков такая, что отрезки не пересекаются между собой и покрывают все $$$m$$$ клеток. Каждый отрезок содержит описание слова в соответствующих клетках.
Особенность в том, что подсказки на самом деле две: одна последовательность находится в строке над клетками для букв, а другая — под ней. Когда эти последовательности разные, они помогают разрешить неоднозначность в ответах.
Дан словарь из $$$n$$$ слов, каждое слово состоит из строчных латинских букв. Все слова попарно различны.
Экземпляр чайнворда — это следующая тройка:
- строка из $$$m$$$ строчных латинских букв;
- первая подсказка: последовательность отрезков такая, что буквы, соответствующие каждому отрезку, составляют некоторое слово из словаря;
- вторая подсказка: еще одна последовательность отрезков такая, что буквы, соответствующие каждому отрезку, составляют некоторое слово из словаря.
Обратите внимание, что последовательности отрезков не обязаны различаться.
Два экземпляра чайнвордов считаются различными, если различаются их строки, первые подсказки или вторые подсказки.
Посчитайте количество различных экземпляров чайнвордов. Так как их число может быть достаточно велико, выведите его остаток от деления на $$$998\,244\,353$$$.
В первой строке записаны два целых числа $$$n$$$ and $$$m$$$ ($$$1 \le n \le 8$$$, $$$1 \le m \le 10^9$$$) — количество слов в словаре и количество клеток с буквами.
В каждой из следующих $$$n$$$ строк записано одно слово — непустая строка из не более $$$5$$$ строчных латинских букв. Все слова попарно различные.
Выведите одно целое число — количество различных экземпляров чайнвордов длины $$$m$$$ для данного словаря по модулю $$$998\,244\,353$$$.
3 5 ababa ab a
11
2 4 ab cd
4
5 100 a aa aaa aaaa aaaaa
142528942
Здесь приведены все примеры различных чайнвордов для первого примера:
Красные полоски над буквами означают отрезки первой подсказки, синие полоски под буквами означают отрезки второй подсказки.
Во втором примере возможные строки: «abab», «abcd», «cdab» и «cdcd». Все подсказки — это отрезки, которые покрывают первые две буквы и последние две буквы.
