19067번 - Binary Strings 다국어

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

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