E - RowCol/ColRow Sort 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MB

配点 : 1400 点

問題文

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}) が与えられます。次の 2 条件をともに満たす 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

条件を満たす行列は次の 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

Score : 1400 points

Problem Statement

Consider the following operations on an H\times W matrix A = (A_{i,j}) (1\leq i\leq H, 1\leq j\leq W).

  • Row-sort: Sort every row in ascending order. That is, sort A_{i,1},\ldots,A_{i,W} in ascending order for every i.
  • Column-sort: Sort every column in ascending order. That is, sort A_{1,j},\ldots,A_{H,j} in ascending order for every j.

You are given an H\times W matrix B = (B_{i,j}). Find the number of H\times W matrices A that satisfy both of the following conditions, modulo 998244353.

  • Performing row-sort and then column-sort on A produces B.
  • Performing column-sort and then row-sort on A produces B.

Constraints

  • 1\leq H, W\leq 1500
  • 0\leq B_{i,j}\leq 9
  • B_{i,j}\leq B_{i,j+1}, for any 1\leq i\leq H and 1\leq j\leq W - 1.
  • B_{i,j}\leq B_{i+1,j}, for any 1\leq j\leq W and 1\leq i\leq H - 1.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

H W
B_{1,1} B_{1,2} \ldots B_{1,W}
\vdots
B_{H,1} B_{H,2} \ldots B_{H,W}

Output

Print the number of matrices A that satisfy the conditions, modulo 998244353.

Sample Input 1

2 2
0 0
1 2

Sample Output 1

4

The four matrices that satisfy the conditions are:

\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}.

We can verify that \begin{pmatrix}2&1\\0&0\end{pmatrix}, for example, satisfies the conditions as follows.

  • Performing row-sort and then column-sort: \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}.

  • Performing column-sort and then row-sort:\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}.

Sample Input 2

3 3
0 1 3
2 4 7
5 6 8

Sample Output 2

576

\begin{pmatrix}5&7&6\\3&0&1\\4&8&2\end{pmatrix}, for example, satisfies the conditions, which can be verified as follows.

  • Performing row-sort and then column-sort: \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}.

  • Performing column-sort and then row-sort: \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}.

Sample Input 3

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

Sample Output 3

10440

Sample Input 4

1 7
2 3 3 6 8 8 9

Sample Output 4

1260