P16314 [ICPC 2023 Jinan R] 来自知识的礼物

在学习完由理查德·彭和桑托什·文帕拉编写的论文《Solving Sparse Linear Systems Faster than Matrix Multiplication》后，小青鱼变得痴迷于一切稀疏的东西，比如稀疏矩阵。在这里，一个稀疏矩阵指零项的数量远高于非零项的矩阵。现在，小青鱼想到了一个有关二进制稀疏矩阵的问题，希望您能着手解决。 给定一个 $r$ 行 $c$ 列的二进制矩阵（一个仅包含 $0$ 和 $1$ 的矩阵），对于每一行您可以选择是否进行反转。求选择一些行进行反转的方案数（允许不选择任何行），使得每一列至多有一个 $1$。称两种方案是不同的，若有一行在其中一种方案里被选择，而在另一种方案里没有被选择。 本题中，反转一行的含义是这样的：设第 $i$ 行从第一列到最后一列的元素依次为 $b_{i, 1}, b_{i, 2}, \cdots, b_{i, c}$。如果您反转了第 $i$ 行，则它将变为 $b_{i, c}, b_{i, c - 1}, \cdots, b_{i, 1}$。

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据： 第一行输入两个整数 $r$ 和 $c$（$1 \le r, c \le 10^6$，$1 \le r \times c \le 10^6$）表示矩阵的行数和列数。 对于接下来 $r$ 行，第 $i$ 行输入一个字符串 $b_{i,1}b_{i,2}\cdots b_{i,c}$（$b_{i,j} \in \{0, 1\}$），其中 $b_{i,j}$ 表示矩阵第 $i$ 行第 $j$ 列的元素。 保证所有数据 $r\times c$ 之和不超过 $10^6$。

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

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