{"raw_statement":[{"iden":"problem statement","content":"Consider the following operations on an $H\\times W$ matrix $A = (A_{i,j})$ ($1\\leq i\\leq H, 1\\leq j\\leq W$).\n\n*   **Row-sort**: Sort every row in ascending order. That is, sort $A_{i,1},\\ldots,A_{i,W}$ in ascending order for every $i$.\n*   **Column-sort**: Sort every column in ascending order. That is, sort $A_{1,j},\\ldots,A_{H,j}$ in ascending order for every $j$.\n\nYou 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$.\n\n*   Performing row-sort and then column-sort on $A$ produces $B$.\n*   Performing column-sort and then row-sort on $A$ produces $B$."},{"iden":"constraints","content":"*   $1\\leq H, W\\leq 1500$\n*   $0\\leq B_{i,j}\\leq 9$\n*   $B_{i,j}\\leq B_{i,j+1}$, for any $1\\leq i\\leq H$ and $1\\leq j\\leq W - 1$.\n*   $B_{i,j}\\leq B_{i+1,j}$, for any $1\\leq j\\leq W$ and $1\\leq i\\leq H - 1$.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$H$ $W$\n$B_{1,1}$ $B_{1,2}$ $\\ldots$ $B_{1,W}$\n$\\vdots$\n$B_{H,1}$ $B_{H,2}$ $\\ldots$ $B_{H,W}$"},{"iden":"sample input 1","content":"2 2\n0 0\n1 2"},{"iden":"sample output 1","content":"4\n\nThe four matrices that satisfy the conditions are:\n$\\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}$.\nWe can verify that $\\begin{pmatrix}2&1\\\\0&0\\end{pmatrix}$, for example, satisfies the conditions as follows.\n\n*   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}$.\n    \n*   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}$."},{"iden":"sample input 2","content":"3 3\n0 1 3\n2 4 7\n5 6 8"},{"iden":"sample output 2","content":"576\n\n$\\begin{pmatrix}5&7&6\\\\3&0&1\\\\4&8&2\\end{pmatrix}$, for example, satisfies the conditions, which can be verified as follows.\n\n*   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}$.\n    \n*   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}$."},{"iden":"sample input 3","content":"3 5\n0 0 0 1 1\n0 0 1 1 2\n0 1 1 2 2"},{"iden":"sample output 3","content":"10440"},{"iden":"sample input 4","content":"1 7\n2 3 3 6 8 8 9"},{"iden":"sample output 4","content":"1260"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}