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