問題文

$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