考虑转化题意，设原来题面中的网格为 a，设 f(i, j) 表示 a 第 i 行第 j 列中的最小值，设网格 b_{n, m} 满足 \forall b_{i, j} \le f(i, j)，求 (a, b) 的个数。不难发现这就是对原来的每个 a 的积的一个转化。考虑 dp 计数，第一维从小到大枚举值域，设 dp_{x, i, j} 表示 a 有 i 行的最大值已经确定且小于等于 x，b 有 j 列的最小值确定了且小于等于 x。下文为了方便表示使用了滚动数组，f_{i, j} 表示上一状态，dp_{i, j} 表示转移到的新的状态。
值域枚举到 x，考虑确定 b 的一列的的最小值为 x，当然转移前要 f \gets dp。考虑计算贡献，考虑哪些位置的值被确定了，对于 a，对于已确定了的 i 行，他们的取值一定是 [x, k]，有 (k - x + 1) ^ i。对于 b，有 n - i 个位置的行还没有被钦定最小值，那么他们都可以取到 [0, x]，并且由于一列最大值为 x 那么一定要有一个是 x，方案数为 x ^ {n - i} - (x - 1) ^ {n - i}。枚举确定了 t 列，有转移：
然后再 f \gets dp，考虑确定 a 的一些行的最大值为 x。类似的计算贡献，首先考虑给 b 的一些位置填，那些所在行还没有被确定最大值的位置有 m - j 个，他们的方案数为 x ^ {m - j}；然后对于 a 的确定了最小值所在列的最小值的位置，他们可以取到 [x, k]，且至少要有一个 x，有方案数 (k - x + 1) ^ j - (k - x) ^ j。枚举确定了 t 行，显然有：