아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

금지된 단어

시간 제한2초메모리 제한512 MB

요약
금지된 부분 문자열을 하나도 포함하지 않는 길이 L의 문자열 개수를 998244353으로 나눈 나머지로 구한다. L은 10^9까지 커질 수 있다.
난이도

어려움10점 중 8점

유형
문자열 매칭, 트라이, 동적 계획법, 행렬
정답자
아직 제출이 없습니다

문제

알파벳 소문자로 이루어진 단어 목록이 주어진다. 길이가 LL인 단어 중에서 목록에 있는 어떤 단어도 부분 문자열로 포함하지 않는 것의 개수를 구하시오.

답이 매우 클 수 있으므로 998 244 353998\,244\,353으로 나눈 나머지를 출력한다.

입력

첫째 줄에 두 정수 bb와 LL이 주어진다 (1≤b≤1001 \le b \le 100; 1≤L≤109+71 \le L \le 10^9+7). bb는 목록에 있는 단어의 수이고, LL은 관심 있는 단어의 길이이다.

다음 bb개 줄에 각각 알파벳 소문자로 이루어진 비어 있지 않은 단어가 하나씩 주어진다. 단어는 서로 다르다. 단어들의 총 길이는 100100 이하이다.

출력

길이가 LL인 단어 중에서 목록에 있는 어떤 단어도 부분 문자열로 포함하지 않는 것의 개수를 998 244 353998\,244\,353으로 나눈 나머지를 출력한다.

예제3

  1. 예제 1

    입력
    3 1
    a
    c
    m
    
    예상 출력
    23
    
  2. 예제 2

    입력
    4 2
    i
    cp
    pc
    cc
    
    예상 출력
    622
    
  3. 예제 3

    입력
    4 12
    china
    russia
    bytedance
    mw
    
    예상 출력
    558811200