Rikka with String

Problem Description

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them: Yuta has $n$ $01$ strings $s_i$, and he wants to know the number of $01$ antisymmetric strings of length $2L$ which contain all given strings $s_i$ as continuous substrings. A $01$ string $s$ is antisymmetric if and only if $s[i] \neq s[|s|-i+1]$ for all $i \in [1,|s|]$. It is too difficult for Rikka. Can you help her? In the second sample, the strings which satisfy all the restrictions are $000111,001011,011001,100110$.

Input

The first line contains a number $t(1 \leq t \leq 5)$, the number of the testcases. For each testcase, the first line contains two numbers $n,L(1 \leq n \leq 6, 1 \leq L \leq 100)$. Then $n$ lines follow, each line contains a $01$ string $s_i(1 \leq |s_i| \leq 20)$.

Output

For each testcase, print a single line with a single number -- the answer modulo 998244353.

Sample Input

2
2 2
011
001
2 3
011
001

Sample Output

1
4

Source

2017 Multi-University Training Contest - Team 5

https://acm.hdu.edu.cn/showproblem.php?pid=6086