设 $0/1$ 串有 $cnt$ 个 $0$，那么设 $f_{i,j}$ 表示操作了 $i$ 次之后前 $m$ 个元素中有 $j$ 个 $0$。

显然有 $f_{x,0}=1$，其中 $x$ 是原串中前 $m$ 个位置中 $0$ 的个数。

转移有一下可能性：

• 前面的 $1$ 与后面的 $0$ 交换，有 $(m-j)^2$ 种方案，转移到 $f_{i+1,j+1}$。
• 前面的 $0$ 与豆面的 $1$ 交换，有 $j\times (n-2\times m+j)$ 种方案，转移到 $f_{i+1,j-1}$。
• 其他的情况都不会影响，直接转移到 $f_{i+1,j}$。

那么就有：

$f_{i+1,j+1}\gets f_{i+1,j+1}+f_{i,j}\times (m-j)^2$

$f_{i+1,j-1}\gets f_{i+1,j-1}\times j\times(n-2\times m+j)$

$f_{i+1,j}\gets f_{i+1,j}+f_{i,j}\times (n^2-(m-j)^2-j\times (n-2\times m+j))$

写出矩阵，跑矩阵快速幂，时间复杂度为 $O(n^3\log k)$，其实跑不满因为 $0$ 太多了。