分数: 500 点
问题陈述
有一个整数序列 S 长度 N。最初,所有元素 S 是 0.
还给你两个长度的整数序列 Q: P=(P_1,P_2,\dots,P_Q) 和 V=(V_1,V_2,\dots,V_Q).
Snuke想要表演 Q 对序列的操作 S 按顺序。的 i第次操作如下:
- 执行以下操作之一:
- 替换每个元素 S_1, S_2, \dots, S_{P_i} 与 V_i。但是,在执行此操作之前,如果其中有一个元素 S_1, S_2, \dots, S_{P_i} 严格大于 V_i,Snuke 会开始哭泣。
- 替换每个元素 S_{P_i}, S_{P_i+1}, \dots, S_N 与 V_i。但是,在执行此操作之前,如果其中有一个元素 S_{P_i}, S_{P_i+1}, \dots, S_N 严格大于 V_i,Snuke 会开始哭泣。
查找序列的数量 Q Snuke 可以执行所有操作而不哭的操作,模数 998244353.
区分两个操作序列当且仅当存在 1 \leq i \leq Q 这样的选择 i-th 操作不同。
约束
- 2 \leq N \leq 5000
- 1 \leq Q \leq 5000
- 1 \leq P_i \leq N
- 1 \leq V_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N Q P_1 V_1 P_2 V_2 \vdots P_Q V_Q
输出
将答案打印为整数。
示例输入 1
8 3 1 8 8 1 2 1
示例输出 1
1
Snuke可以不哭的执行以下三种操作:
- 替换 S_1 与 8.
- 替换 S_8 与 1.
- 替换 S_2, S_3, \dots, S_8 与 1.
没有其他操作序列满足条件,所以答案是 1。例如,如果他替换 S_1, S_2, \dots, S_8 与 8 第一次手术时,无论选择如何,第二次手术时他都会哭。
示例输入 2
8 3 8 1 1 8 1 2
示例输出 2
0
无论前两次手术他怎么做,第三次手术他都会哭。
示例输入 3
241 82 190 3207371 229 3639088 61 4428925 84 17258698 34 42692503 207 59753183 180 67198566 78 99285033 60 102449991 234 122146510 111 126959145 141 152331579 78 159855439 11 169658471 22 189991287 37 204602946 73 209329065 72 215363269 152 236450854 175 237822921 22 261431608 144 252550201 54 268889550 238 276997357 69 313065279 226 330144323 6 335788783 126 345410019 220 348318997 166 365778763 142 382251905 200 406191336 234 392702679 83 409660987 183 410908761 142 445707116 205 470279207 230 486436406 156 494269002 113 495687706 200 500005738 162 505246499 201 548652987 86 449551554 62 459527873 32 574001635 230 601073337 175 610244315 174 613857555 181 637452273 158 637866397 148 648101378 172 646898076 144 682578257 239 703460335 192 713255331 28 727075136 196 730768166 111 751850547 90 762445737 204 762552166 72 773170159 240 803415865 32 798873367 195 814999380 72 842641864 125 851815348 116 858041919 200 869948671 195 873324903 5 877767414 105 877710280 150 877719360 9 884707717 230 880263190 88 967344715 49 977643789 167 979463984 70 981400941 114 991068035 94 991951735 141 995762200
示例输出 3
682155965
记住对计数取模 998244353.