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}$$$.
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$$$.
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)$$$.
33 50110010001000102 1112 3001001
4 0 2
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$$$.
Name |
---|