那头是头！

1 个月了都没有简单做法，急了。

先考虑怎么求总的方案数。于是先随便设一个 $f_{n,m}$ 为大小为 $n\times m$ 的合法矩阵的方案数。

一个方案合法的条件是对于任意一个 $1$，它所在的行前缀均为 $1$ 或列前缀均为 $1$。

所以很自然地枚举当前矩阵最后一行的极长前缀 $1$ 个数，再枚举后面的 $1$ 的位置，合法转移即钦定后面这些 $1$ 的位置对应的列全为 $1$ 的方案数。

可以发现对于一个 $n\times m$ 的矩阵，钦定其中 $p$ 列为 $1$ 的方案与 $n\times (m-p)$ 的矩阵的方案形成双射。

所以直接得到一个 $O(nm^3)$ 的转移。

可以类似转移得到方案的 $1$ 的个数的和。

即

交换和式后用上指标求和优化到 $O(nm^2)$，因为 $nm=S\le 2\times 10^5$，所以复杂度不超过 $O(S\sqrt{S})$，可过。

转移是卷积形式还可以优化成 $O(nm\log m)$，但是不重要了。