题目描述

在学习完由理查德·彭和桑托什·文帕拉编写的论文《Solving Sparse Linear Systems Faster than Matrix Multiplication》后，小青鱼变得痴迷于一切稀疏的东西，比如稀疏矩阵。在这里，一个稀疏矩阵指零项*的数量远高于非零项的矩阵。现在，小青鱼想到了一个有关二进制稀疏矩阵的问题，希望您能着手解决。

给定一个 $r$ 行 $c$ 列的二进制矩阵(一个仅包含 $0$ 和$1$ 的矩阵)，对于每一行您可以选择是否进行反转。求选择一些行进行反转的方案数(允许不选择任何行)，使得每一列至多有一个1。称两种方案是不同的，若有一行在其中一种方案里被选择，而在另一种方案里没有被选择。

本题中，反转一行的含义是这样的:设第 $i$ 行从第一列到最后一列的元素依次为 $b_{i,1}, b_{i,2},· · ·, b_{i,c}$ 。如果您反转了第 $i$ 行，则它将变为 $b_{i,c}, b_{i,c−1},· · ·, b_{i,1}$ 。

输入格式

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据:第一行输入两个整数 $r$ 和$c$ $(1≤r, c≤10^6，1≤r×c≤10^6)$表示矩阵的行数和列数。

对于接下来 $r$ 行，第 $i$ 行输入一个字符串$b_{i,1},b_{i,2}· · ·b_{i,c}(b_{i,j}∈ {0,1})$，其中 $b_{i,j}$ 表示矩阵第 $i$ 行第 $j$ 列的元素。

保证所有数据$r×c$之和不超过$10^6$。

输出格式

每组数据输出一行一个整数表示方案数。由于答案可能很大，请将答案对$(10^9+ 7)$取模后输出。

样例

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

4
0
2

样例解释

对于第一组样例数据，选择的行的集合可以是空集，${1, 3}，{2}$ 或 ${1,2,3}$ 。所以答案是 $4$。