AT_agc057_e [AGC057E] RowCol/ColRow Sort

给定一个 $H\times W$ 的矩阵 $A = (A_{i,j})$（$1\leq i\leq H,\ 1\leq j\leq W$），定义如下两种操作： - **行排序**：对每一行进行升序排序。即对于所有 $i$，将 $A_{i,1},\ldots,A_{i,W}$ 升序排列。 - **列排序**：对每一列进行升序排序。即对于所有 $j$，将 $A_{1,j},\ldots,A_{H,j}$ 升序排列。 给定一个 $H\times W$ 的矩阵 $B = (B_{i,j})$，请计算满足以下两个条件的 $H\times W$ 矩阵 $A$ 的总数，并对 $998244353$ 取模： - 对 $A$ 先进行行排序再进行列排序，结果等于 $B$。 - 对 $A$ 先进行列排序再进行行排序，结果等于 $B$。

输入通过标准输入给出，格式如下： > $H$ $W$ > $B_{1,1}$ $B_{1,2}$ $\ldots$ $B_{1,W}$ > $\vdots$ > $B_{H,1}$ $B_{H,2}$ $\ldots$ $B_{H,W}$

输出满足条件的矩阵 $A$ 的总数，对 $998244353$ 取模后的结果。

### 限制条件 - $1\leq H,\ W\leq 1500$ - $0\leq B_{i,j}\leq 9$ - 对任意 $1\leq i\leq H$ 及 $1\leq j\leq W-1$，有 $B_{i,j}\leq B_{i,j+1}$ - 对任意 $1\leq j\leq W$ 及 $1\leq i\leq H-1$，有 $B_{i,j}\leq B_{i+1,j}$ - 输入的所有值均为整数 ### 样例解释 1 满足条件的矩阵有如下 $4$ 个：$\begin{pmatrix}0&0\\1&2\end{pmatrix}$，$\begin{pmatrix}0&0\\2&1\end{pmatrix}$，$\begin{pmatrix}1&2\\0&0\end{pmatrix}$，$\begin{pmatrix}2&1\\0&0\end{pmatrix}$。例如，$\begin{pmatrix}2&1\\0&0\end{pmatrix}$ 满足条件的验证如下： - 先行排序再列排序：$\begin{pmatrix}2&1\\0&0\end{pmatrix}\to\begin{pmatrix}1&2\\0&0\end{pmatrix}\to\begin{pmatrix}0&0\\1&2\end{pmatrix}$。 - 先列排序再行排序：$\begin{pmatrix}2&1\\0&0\end{pmatrix}\to\begin{pmatrix}0&0\\2&1\end{pmatrix}\to\begin{pmatrix}0&0\\1&2\end{pmatrix}$。 ### 样例解释 2 例如 $\begin{pmatrix}5&7&6\\3&0&1\\4&8&2\end{pmatrix}$ 满足条件，验证如下： - 先行排序再列排序：$\begin{pmatrix}5&7&6\\3&0&1\\4&8&2\end{pmatrix}\to\begin{pmatrix}5&6&7\\0&1&3\\2&4&8\end{pmatrix}\to\begin{pmatrix}0&1&3\\2&4&7\\5&6&8\end{pmatrix}$。 - 先列排序再行排序：$\begin{pmatrix}5&7&6\\3&0&1\\4&8&2\end{pmatrix}\to\begin{pmatrix}3&0&1\\4&7&2\\5&8&6\end{pmatrix}\to\begin{pmatrix}0&1&3\\2&4&7\\5&6&8\end{pmatrix}$。 由 ChatGPT 4.1 翻译