问题描述

考虑对一个 $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$。

约束条件

• $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}$。
• 输入中的所有值均为整数。

输入格式

输入以以下格式从标准输入给出：

$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

2 2
0 0
1 2

样例输出 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

3 3
0 1 3
2 4 7
5 6 8

样例输出 2

576

例如，$\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}$。

样例输入 3

3 5
0 0 0 1 1
0 0 1 1 2
0 1 1 2 2

样例输出 3

10440

样例输入 4

1 7
2 3 3 6 8 8 9

样例输出 4

1260