解题思路

可达性分析

由于允许任意次相邻格子间交换“0”和“1”，且“1”们不可区分，只要保持“1”的总数 $K$ 不变，就能把这 $K$ 个“1”放到任意 $K$ 个格子上。因此，可达的所有状态就是：在 $N=n\times m$ 个格子中任取 $K$ 个位置放“1”。

奇偶性判定

定义权值

$W=\frac12\sum_{u\sim v}|x_u-x_v|.$

题目内容

有一个$n$行$m$ 列的网格，我们使用$(i,j)$ 表示网格中从上往下数第$i$行和从左往右数第$j$列的单元格。每个方格的值为$0$或$1$，且任何操作均不得超出网格边界。

我们定义网格的权值为网格中每个单元格与其相邻且数值不同的单元格个数之和的一半，网格的奇偶性为该权值的奇偶性。

$Tk$ 可以任意次进行如下操作:

• 选择两个相邻的单元格交换它们的值

$Tk$想知道经过任意次操作后，能够得到多少种不同的网格为偶网格.

在这里，当$|x-x'|+|y-y'|=1$时，单元格$(x,y)$与$(x',y')$被认为是相邻的.

我们认为若两个网格至少存在一个相同位置的单元格数值不同，则认为这两个网格不同.

由于答案可能很大，请将答案对$10^9+7$取模后输出

输入描述

第一行输入两个整数$n，m(2≤n,m,n×m ≤5×10^5)$，表示网格的行数和列数.

接下来输入$n$ 行，每行$m$ 个整数$a_{i,j}$($a_{i,j}$∈ {$0,1$})，表示初始时每个单元格的值.

输出描述

输出一个整数，表示不同偶矩阵的数量

由于答案可能很大，请将答案对$10^9+7$取模后输出

样例1

输入

2 2
1 0
0 1

输出

6

说明

• 满足条件的矩阵有:

  $\begin{bmatrix}1\ 0 \\1\ 0 \end{bmatrix}$、$\begin{bmatrix}1\ 0 \\0\ 1 \end{bmatrix}$、$\begin{bmatrix}1\ 1 \\0\ 0 \end{bmatrix}$、$\begin{bmatrix}0\ 1 \\1\ 0 \end{bmatrix}$、$\begin{bmatrix}0\ 1 \\0\ 1 \end{bmatrix}$、$\begin{bmatrix}0\ 0 \\1\ 1 \end{bmatrix}$