分数: 1400 点
问题陈述
考虑以下操作 H\times W 矩阵 A = (A_{i,j}) (1\leq i\leq H, 1\leq j\leq W).
- 行排序:按升序对每一行进行排序。也就是说,排序 A_{i,1},\ldots,A_{i,W} 按升序排列每个 i.
- 列排序:按升序对每列进行排序。也就是说,排序 A_{1,j},\ldots,A_{H,j} 按升序排列每个 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
- B_{i,j}\leq B_{i,j+1},对于任何 1\leq i\leq H 和 1\leq j\leq W - 1.
- B_{i,j}\leq B_{i+1,j},对于任何 1\leq j\leq W 和 1\leq i\leq H - 1.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
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