P16314 [ICPC 2023 Jinan R] A Gift from Knowledge

After studying the paper *Solving Sparse Linear Systems Faster than Matrix Multiplication* by Richard Peng and Santosh Vempala, Xiaoqingyu became obsessed with everything sparse, such as sparse matrices. Here, a sparse matrix means a matrix where the number of zero entries is much larger than the number of non-zero entries. Now, Xiaoqingyu has come up with a problem about binary sparse matrices and hopes you can solve it. You are given a binary matrix with $r$ rows and $c$ columns (a matrix containing only $0$ and $1$). For each row, you may choose whether to reverse it. Find the number of ways to choose some rows to reverse (choosing no rows is allowed) such that each column contains at most one $1$. Two ways are considered different if there exists a row that is chosen in one way but not chosen in the other. In this problem, reversing a row means the following: suppose the elements in row $i$ from the first column to the last column are $b_{i, 1}, b_{i, 2}, \cdots, b_{i, c}$. If you reverse row $i$, it becomes $b_{i, c}, b_{i, c - 1}, \cdots, b_{i, 1}$.

There are multiple test cases. The first line 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$), representing the number of rows and columns of the matrix. For the next $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 in row $i$ and column $j$ of the matrix. It is guaranteed that the sum of $r \times c$ over all test cases does not exceed $10^6$.

For each test case, output one line containing an integer representing the number of ways. Since the answer may be large, output it modulo $(10^9 + 7)$.

For the first sample test case, the set of chosen rows can be the empty set, $\{1, 3\}$, $\{2\}$, or $\{1, 2, 3\}$. Therefore, the answer is $4$. Translated by ChatGPT 5