考虑容斥，只需要计算钦定 $i$ 个鞍点的方案数。

这 $i$ 个鞍点一定在不同的行列，确定它们的值之后，剩下的值的方案数很容易确定：如果一个数所在的行列的鞍点的权值分别为 $a,b$（不存在视为 $k+1$，那么它的方案数就是 $\min\{a,b\}-1$。

于是我们可以对其进行 DP，从小到大加数，$dp(v,i)$ 表示已经考虑了不超过 $v$ 的数，有 $i$ 个鞍点，同一行或同一列存在鞍点的数的方案数，则 $dp(k,i)\cdot k^{(n-i)(m-i)}$ 就是所求。

转移如下： $$ dp(v+1,i)=\sum_{j=0}^i dp(v,j){n-j\choose i-j}{m-j\choose i-j}(i-j)!v^{(n-j)(m-j)-(n-i)(m-i)-(i-j)} $$ 时间复杂度 $O(nmk)$。