{"raw_statement":[{"iden":"problem statement","content":"There is an integer sequence $S$ of length $N$. Initially, all elements of $S$ are $0$.\nYou are also given two integer sequences of length $Q$: $P=(P_1,P_2,\\dots,P_Q)$ and $V=(V_1,V_2,\\dots,V_Q)$.\nSnuke wants to perform $Q$ operations on the sequence $S$ in order. The $i$\\-th operation is as follows:\n\n*   Perform one of the following:\n    *   Replace each of the elements $S_1, S_2, \\dots, S_{P_i}$ with $V_i$. However, before this operation, if there is an element among $S_1, S_2, \\dots, S_{P_i}$ that is strictly greater than $V_i$, Snuke will start crying.\n    *   Replace each of the elements $S_{P_i}, S_{P_i+1}, \\dots, S_N$ with $V_i$. However, before this operation, if there is an element among $S_{P_i}, S_{P_i+1}, \\dots, S_N$ that is strictly greater than $V_i$, Snuke will start crying.\n\nFind the number of sequences of $Q$ operations where Snuke can perform all operations without crying, modulo $998244353$.\nTwo sequences of operations are distinguished if and only if there is $1 \\leq i \\leq Q$ such that the choice for the $i$\\-th operation is different."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 5000$\n*   $1 \\leq Q \\leq 5000$\n*   $1 \\leq P_i \\leq N$\n*   $1 \\leq V_i \\leq 10^9$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $Q$\n$P_1$ $V_1$\n$P_2$ $V_2$\n$\\vdots$\n$P_Q$ $V_Q$"},{"iden":"sample input 1","content":"8 3\n1 8\n8 1\n2 1"},{"iden":"sample output 1","content":"1\n\nSnuke can perform the three operations without crying as follows:\n\n*   Replace $S_1$ with $8$.\n*   Replace $S_8$ with $1$.\n*   Replace $S_2, S_3, \\dots, S_8$ with $1$.\n\nNo other sequences of operations satisfy the conditions, so the answer is $1$. For example, if he replaces $S_1, S_2, \\dots, S_8$ with $8$ in the first operation, he will cry in the second operation regardless of the choice."},{"iden":"sample input 2","content":"8 3\n8 1\n1 8\n1 2"},{"iden":"sample output 2","content":"0\n\nNo matter how he performs the first two operations, he will cry in the third operation."},{"iden":"sample input 3","content":"241 82\n190 3207371\n229 3639088\n61 4428925\n84 17258698\n34 42692503\n207 59753183\n180 67198566\n78 99285033\n60 102449991\n234 122146510\n111 126959145\n141 152331579\n78 159855439\n11 169658471\n22 189991287\n37 204602946\n73 209329065\n72 215363269\n152 236450854\n175 237822921\n22 261431608\n144 252550201\n54 268889550\n238 276997357\n69 313065279\n226 330144323\n6 335788783\n126 345410019\n220 348318997\n166 365778763\n142 382251905\n200 406191336\n234 392702679\n83 409660987\n183 410908761\n142 445707116\n205 470279207\n230 486436406\n156 494269002\n113 495687706\n200 500005738\n162 505246499\n201 548652987\n86 449551554\n62 459527873\n32 574001635\n230 601073337\n175 610244315\n174 613857555\n181 637452273\n158 637866397\n148 648101378\n172 646898076\n144 682578257\n239 703460335\n192 713255331\n28 727075136\n196 730768166\n111 751850547\n90 762445737\n204 762552166\n72 773170159\n240 803415865\n32 798873367\n195 814999380\n72 842641864\n125 851815348\n116 858041919\n200 869948671\n195 873324903\n5 877767414\n105 877710280\n150 877719360\n9 884707717\n230 880263190\n88 967344715\n49 977643789\n167 979463984\n70 981400941\n114 991068035\n94 991951735\n141 995762200"},{"iden":"sample output 3","content":"682155965\n\nRemember to take the count modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}