题解

题目描述

给定一个 $n$ 行 $m$ 列的二元网格（每个格子值为 $0$ 或 $1$），用 $(i,j)$ 表示第 $i$ 行第 $j$ 列的格子。允许的操作是任意次选择两个相邻格子（上下或左右）并交换它们的值。定义格子的权值为该格子与相邻格子中数值不同的个数，网格的奇偶性为所有格子权值之和的奇偶性。给定初始网格，问在经过任意次上述操作后，能够得到多少种不同的偶网格（即权值和为偶数的网格）的配置数。结果对 $10^9+7$ 取模。

思路

1. 可达状态分析
   网格连通且只允许相邻格子交换，交换操作可在连通图上生成对所有格子值的任意排列。因此，所有与初始网格拥有相同的 $1$ 的个数 $k$ 的二元矩阵均可达到。

题目内容

有一个 $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

说明

下面给出这 $6$ 种不同偶矩阵的方案：