本题的核心要求是计算删除元素后能得到多少种不同的矩阵。

在 $01$ 矩阵的某一行中，删除一个元素后得到的剩余字符串，仅与被删除元素所在的 “连续相同字符块” 有关。例如，对于字符串 00100，删除第一个 0 或第二个 0 得到的字符串都是 0100。为了避免重复计数，我们需要为每一种合法的矩阵对应一个唯一的删除路径。

对于任意一个合法的目标矩阵，可能存在多条满足 $\vert{}a_i-a_{i-1}\vert{}\le K$ 的路径 $a_1, a_2, \dots, a_n$。

在所有能生成同一个矩阵的路径中，必然存在一条在各个位置上取值尽可能大的“最右路径”。这条唯一的最大路径满足以下右紧凑条件：

对于每一行 $i$，设删除的位置为 $a_i$，以下三个条件中至少有一个成立：

• $a_i$ 是当前连续字符块的最右侧元素（即 $a_i = m$ 或 $A[i][a_i] \neq A[i][a_i+1]$）。
• $i > 1$ 且 $a_i - a_{i-1} = K$（受限于左侧的最大跨度，无法再往右移动）。
• $i < n$ 且 $a_i - a_{i+1} = K$（受限于右侧的最大跨度，无法再往右移动）。

我们将 “$a_i$ 是当前块的最右侧元素” 记为布尔条件 $P(i, a_i)$。那么约束可以转化为：每个位置 $i$ 必须满足 $P(i, a_i) \lor (a_i - a_{i-1} == K) \lor (a_i - a_{i+1} == K)$。

我们可以设计一个动态规划来统计满足上述 “右紧凑条件” 的路径数量。

定义状态 $f[i][j][0/1]$ 表示处理到第 $i$ 行，第 $i$ 行删除的列索引为 $j$ 时的合法路径数。其中第三维表示前缀是否已经满足了第 $i$ 行的条件。

• $f[i][j][1]$：表示 $P(i, j) \lor (j - k == K)$ 为真（$k$ 为上一行选择的列），即仅靠 $i$ 行本身及之前的选择已经满足条件，不需要第 $i+1$ 行来拯救。
• $f[i][j][0]$：表示前缀未能满足条件。此时必须利用第 $i+1$ 行来满足，强制要求 $j - a_{i+1} == K$，即 $a_{i+1} = j - K$。

设上一行选择的列尾 $k$：

如果上一行的状态是 $f[i-1][k][0]$，则强制要求当前行的列 $j$ 必须满足 $k-j=K$，即 $k=j+K$。

这部分转移的方案数记为 $x=f[i-1][j+k][0]$。

如果上一行的状态是 $f[i-1][k][1]$，上一行已满足条件，当前行 $j$ 可以任意选取满足 $|j-k|\le K$ 的位置。

这部分的方案数之和为 $sum=\sum_{k=j-K}^{j+K}f[i-1][k][1]$。

对于当前行来说，如果 $P(i,j)$ 为真，无论上一行怎么选，当前行都满足条件，因此：

$$\begin{aligned}f[i][j][1]&=(sum+x)\pmod{10^9+7}\\f[i][j][0]&=0\end{aligned}$$

如果 $P(i,j)$ 为假，当前行要满足条件，必须依赖 $j-k=K$，即 $k=j-K$。这部分的方案数为 $y=f[i-1][j-k][1]$。其余情况都会导致当前行不满足条件：

$$\begin{aligned}f[i][j][1]&=y\pmod{10^9+7}\\f[i][j][0]&=(sum-y+x)\pmod{10^9+7}\end{aligned}$$

由于 $n,m \le 3000$，整体时间复杂度为 $O(nm)$。

可以使用滚动数组优化，空间复杂度为 $O(m)$。当然不优化也可以。

声明，本题值域可以不只为 $0/1$。

显然第，这题计数，使用三大法！

DP, DFS, 计算

这题显然数学计算无法表示，直接 DP!

不难发现，朴素的令 $dp_{i, j}$ 为删除到第 $i$ 行，当前行删除到 $j$，的方案数量显然重复。

类似 CF， 我们令 $same_{i, j}$ 表示第 $i$ 行，删除 $j$ 和 $j-1$ 的相同方案数。

不难发现，此时删除 $j$ 的方案数量是 $dp_{i, j} - same_{i, j}$ 。

不难转移，初始，答案，优化。