시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 11 10 10 90.909%

문제

You are given a list of words consisting of lowercase English letters. Calculate the number of words of length $L$ that do not contain any of the words from the list as a substring.

Since the answer may be too big, print it modulo $998\,244\,353$.

입력

The first line contains two integers $b$ and $L$ ($1 \le b \le 100$; $1 \le L \le 10^9+7$) --- the number of words in the list and word length you are interested in.

Each of the following $b$ lines contains a non-empty word consisting of lowercase English letters. The words are distinct. The total length of the words is not greater than $100$.

출력

Print the number of words of length $L$ that do not contain any word from the list as a substring, modulo $998\,244\,353$.

예제 입력 1

3 1
a
c
m

예제 출력 1

23

예제 입력 2

4 2
i
cp
pc
cc

예제 출력 2

622

예제 입력 3

4 12
china
russia
bytedance
mw

예제 출력 3

558811200