AT_arc182_a [ARC182A] Chmax Rush!

有一个长度为 $N$ 的整数序列 $S$。初始时，$S$ 的所有元素均为 $0$。 另外，给定长度为 $Q$ 的整数序列 $P=(P_1,P_2,\dots,P_Q)$ 和 $V=(V_1,V_2,\dots,V_Q)$。 すぬけ君想要对数列 $S$ 顺次进行 $Q$ 次操作。第 $i$ 次操作如下： - 可以进行以下两种操作之一。 - 将 $S_1,S_2,\dots,S_{P_i}$ 全部替换为 $V_i$。但如果在这次操作前，$S_1,S_2,\dots,S_{P_i}$ 中存在严格大于 $V_i$ 的元素，すぬけ君会哭出来。 - 将 $S_{P_i},S_{P_i+1},\dots,S_N$ 全部替换为 $V_i$。但如果在这次操作前，$S_{P_i},S_{P_i+1},\dots,S_N$ 中存在严格大于 $V_i$ 的元素，すぬけ君会哭出来。 请计算，能够使すぬけ君不哭地完成 $Q$ 次操作的操作序列有多少种，将答案对 $998244353$ 取模。 这里，若存在某个 $1\leq i\leq Q$，使得在第 $i$ 次操作中选择的操作不同，则认为两个操作序列是不同的。

输入按以下格式从标准输入读入。 > $N$ $Q$ $P_1$ $V_1$ $P_2$ $V_2$ $\vdots$ $P_Q$ $V_Q$

请输出一个整数作为答案。

### 数据范围 - $2 \leq N \leq 5000$ - $1 \leq Q \leq 5000$ - $1 \leq P_i \leq N$ - $1 \leq V_i \leq 10^9$ - 输入均为整数 ### 样例解释 1 如下操作可以使すぬけ君不哭地完成 $3$ 次操作： - 将 $S_1$ 替换为 $8$。 - 将 $S_8$ 替换为 $1$。 - 将 $S_2,S_3,\dots,S_8$ 替换为 $1$。 除此之外，没有其他满足条件的操作序列，所以答案为 $1$。例如，如果第 $1$ 次操作选择将 $S_1,S_2,\dots,S_8$ 替换为 $8$，那么第 $2$ 次操作无论选择哪种方式，すぬけ君都会哭出来。 ### 样例解释 2 无论前两次操作如何进行，在第 $3$ 次操作时すぬけ君都会哭出来。 ### 样例解释 3 不要忘记将答案对 $998244353$ 取模。 由 ChatGPT 4.1 翻译