Rikka with String

Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

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

Hint

liuyiding

Source

2017 Multi-University Training Contest - Te

提交代码