이진 문자열

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

요약

길이가 2L인 반대칭 이진 문자열 중 주어진 n개의 이진 문자열을 모두 부분 문자열로 포함하는 개수를 998244353으로 나눈 나머지로 구합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 문자열 매칭, 비트 연산
정답자: 아직 제출이 없습니다

문제

이진 문자열 $s$ 가 반대칭이라는 것은 모든 $i$ ( $1 \leq i \leq |s|$ )에 대해 $s[i] \neq s[|s| - i + 1]$ 을 만족하는 것이다. Yuta는 이진 문자열 $s_i$ 를 $n$ 개 가지고 있다. 그는 길이가 $2L$ 인 반대칭 이진 문자열 중에서 주어진 모든 $s_i$ 를 연속 부분 문자열로 포함하는 것의 개수를 구하려 한다. 답은 $998\,244\,353$ 으로 나눈 나머지를 출력한다.

입력

첫째 줄에 두 정수 $n$ 과 $L$ ( $1 \leq n \leq 6$ , $1 \leq L \leq 100$ )이 주어진다. 이어지는 $n$ 개의 줄에는 각각 0과 1로 이루어진 문자열 $s_i$ ( $1 \leq |s_i| \leq 20$ )가 주어진다.

출력

답을 $998\,244\,353$ 으로 나눈 나머지를 한 줄에 출력한다.

힌트

두 번째 예제에서 모든 조건을 만족하는 문자열은 000111, 001011, 011001, 100110이다.

예제2

예제 1
입력
```
2 2
011
001
```
예상 출력
```
1
```
예제 2
입력
```
2 3
011
001
```
예상 출력
```
4
```