Banned Words

금지어 목록의 어떤 단어도 부분 문자열로 포함하지 않는 길이 L의 문자열 개수를 998244353으로 나눈 나머지로 구합니다.

어려움8트라이동적 계획법문자열 매칭행렬아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제 설명

예제3

문제

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$ .