题目描述

现有一个 $n\times m$ 的 $01$ 矩阵，对于每一行，你可以选择是否将其反转，即 $a_{i,1},a_{i,2},...,a_{i,m}$ 变为 $a_{i,m},a_{i,m-1},...,a_{i,1}$。要求最后每一列至多有一个 $1$，求方案数，对 $10^9+7$ 取模。

两种方案不同，当且仅当存在某一行在其中一种方案中被反转了，在另一种方案中没有被反转。

输入格式

本题有多组数据。第一行输入一个整数 $T$ 表示数据组数，对于每组数据：

第一行输入两个整数 $n,m$。

接下来的 $n$ 行，第 $i$ 行输入一个长为 $m$ 的 $01$ 字符串。

输出格式

每组数据输出一行一个整数，表示方案数对 $10^9+7$ 取模的值。

输入样例

3
3 5
01100
10001
00010
2 1
1
1
2 3
001
001

输出样例

4
0
2

说明提示

样例说明

解释：第一组样例中，可选的行的集合为 $\phi,\{1,3\},\{2\},\{1,2,3\}$。

输入样例 #2

1
1 1
1

输出样例 #2

2

输入样例 #3

1
2 2
00
10

输出样例 #3

4

数据范围

对于 $10\%$ 的数据，$T = 1,1\leq n,m\leq 10$。

对于 $20\%$ 的数据，$T = 1,1\leq n,m\leq 20$。

对于另外 $20\%$ 的数据，$n\leq 5$。

对于另外 $20\%$ 的数据，$m\leq 5$。

对于 $100\%$ 的数据，$1\leq n,m\leq 10^6,1\leq n\times m\leq 10^6,\sum nm\leq 10^6$。