{"problem":{"name":"RowCol/ColRow Sort","description":{"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$). *   **Row-sort**: Sort every row in ascending order. That is, sort $A_{i,1},\\ldots,A_{i,W}","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc057_e"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc057_e","tags":[],"sample_group":[["2 2\n0 0\n1 2","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}$."],["3 3\n0 1 3\n2 4 7\n5 6 8","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}$."],["3 5\n0 0 0 1 1\n0 0 1 1 2\n0 1 1 2 2","10440"],["1 7\n2 3 3 6 8 8 9","1260"]],"created_at":"2026-03-03 11:01:14"}}