Binary Strings

Time limit1sMemory limit512 MB

Summary

Count the antisymmetric binary strings of length 2L that contain each of n given binary strings (n up to 6, length up to 20) as a substring, modulo 998244353.

Level: Hard8 of 10
Topics: Dynamic programming, String matching, Bit manipulation
Solved: No attempts yet

Problem

A binary string $s$ is antisymmetric if $s[i] \neq s[|s| - i + 1]$ for all $i$ with $1 \leq i \leq |s|$ . Yuta has $n$ binary strings $s_i$ . He wants to count the binary antisymmetric strings of length $2L$ that contain every given string $s_i$ as a contiguous substring. Print the count modulo $998\,244\,353$ .

Input

The first line contains two integers $n$ and $L$ ( $1 \leq n \leq 6$ , $1 \leq L \leq 100$ ). Each of the next $n$ lines contains a string $s_i$ ( $1 \leq |s_i| \leq 20$ ) made of the characters 0 and 1.

Output

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

Hint

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

Examples2

Example 1
Input
```
2 2
011
001
```
Expected output
```
1
```
Example 2
Input
```
2 3
011
001
```
Expected output
```
4
```