시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 1 1 1 100.000%

문제

A binary string $s$ is said to be antisymmetric if and only if $s[i] \neq s[|s| - i + 1]$ for all $i \in [1, |s|]$.

Yuta has $n$ binary strings $s_i$, and he wants to know the number of binary antisymmetric strings of length $2 L$ which contain all given strings $s_i$ as continuous substrings. Help him find that number. As the answer can be very large, find it modulo $998\,244\,353$.

입력

The first line of the input contains two integers $n$ and $L$ ($1 \leq n \leq 6$, $1 \leq L \leq 100$). 

Then $n$ lines follow, each line contains a string $s_i$ ($1 \leq |s_i| \leq 20$) consisting of characters "0" and "1".

출력

Print a single line with a single integer: the answer modulo $998\,244\,353$.

예제 입력 1

2 2
011
001

예제 출력 1

1

예제 입력 2

2 3
011
001

예제 출력 2

4

힌트

In the second example, the strings which satisfy all the restrictions are 000111, 001011, 011001 and 100110.