G. Gifts from Knowledge
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

After studying the paper Solving Sparse Linear Systems Faster than Matrix Multiplication by Richard Peng, and Santosh Vempala, Little Cyan Fish becomes obsessed with anything that is sparse. For example, a sparse matrix. Here, a sparse matrix refers to a matrix in which the number of zero elements is much higher than the number of non-zero elements. Now, Little Cyan Fish comes up with a problem about binary sparse matrices and he wants you to try solving it.

Given a binary matrix (a matrix containing only $$$0$$$s and $$$1$$$s) with $$$r$$$ rows and $$$c$$$ columns, you can choose whether to reverse each row or not. Find the number of ways to choose a set of rows to reverse (it is allowed not to choose any row), so that every column has at most one $$$1$$$. Two ways are considered different if a row is chosen in one of them but not the other.

By reversing a row, we mean this: Let the elements on the $$$i$$$-th row be $$$b_{i, 1}, b_{i, 2}, \cdots, b_{i, c}$$$ from the first column to the last column. If you reverse the $$$i$$$-th row, it becomes $$$b_{i, c}, b_{i, c - 1}, \cdots, b_{i, 1}$$$.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:

The first line contains two integers $$$r$$$ and $$$c$$$ ($$$1 \le r, c \le 10^6$$$, $$$1 \le r \times c \le 10^6$$$) indicating the number of rows and columns of the matrix.

For the following $$$r$$$ lines, the $$$i$$$-th line contains a string $$$b_{i,1}b_{i,2}\cdots b_{i,c}$$$ ($$$b_{i,j} \in \{0, 1\}$$$) where $$$b_{i,j}$$$ is the element on the $$$i$$$-th row and the $$$j$$$-th column of the matrix.

It's guaranteed that the sum of $$$r\times c$$$ of all test cases does not exceed $$$10^6$$$.

Output

For each test case output one line containing one integer indicating the number of ways. As the answer might be large, print the answer modulo $$$(10^9 + 7)$$$.

Example
Input
3
3 5
01100
10001
00010
2 1
1
1
2 3
001
001
Output
4
0
2
Note

For the first sample test case, the set of selected rows can be empty, $$$\{1, 3\}$$$, $$$\{2\}$$$ or $$$\{1, 2, 3\}$$$. So the answer is $$$4$$$.