A84813.午枫的填数游戏

小午有一个长度为 $n$ 的序列 $a$ ，起初，序列 $a$ 的元素都为 $0$ 。

现在小午给了小枫 $q$ 个数对 $(p_i,v_i)$ ，要求小枫按顺序执行这 $q$ 个数对，其中每个数对可以按照以下两种方式中的一种进行执行：

• 将序列 $a$ 中 $a_1,a_2,\cdots,a_{p_i}$ 替换为 $v_i$ 。但是在执行这个操作之前，必须保证 $a_1,a_2,\cdots,a_{p_i}$ 所有元素都小于或等于 $v_i$ 。
• 将序列 $a$ 中 $a_{p_i},a_{p_i+1},\cdots,a_{n}$ 替换为 $v_i$ 。但是在执行这个操作之前，必须保证 $a_{p_i},a_{p_i+1},\cdots,a_{n}$ 所有元素都小于或等于 $v_i$ 。

如果对于存在一个数对无法执行，那小枫就会生气。

小午想知道有多少种不同的执行序列可以把 $q$ 个数对执行完，如果无法全部执行，则输出 0 。

当且仅当有 $1\leq i\leq q$ 使得第 $i$ 个执行方式的选择不同时，两个执行序列不同。

第一行输入两个整数 $n,q$ $(2\leq n\leq 5000, 1\leq q\leq 5000)$ ，分别表示序列 $a$ 的长度以及数对数量。

接下来 $q$ 行，每行两个整数 $p_i,v_i$ $(1\leq p_i\leq n,1\leq v_i\leq 10^9)$ ，表示第 $i$ 个数对中的元素。

输出一个整数，表示有多少种不同的执行序列可以把 $q$ 个数对执行完，由于答案可能很大，最终结果对 $998244353$ 取模。

样例1解释

小枫只能进行以下方式执行：

• 将 $a_1$ 替换为 $8$
• 将 $a_8$ 替换为 $1$
• 将 $a_2,a_3,\cdots,a_8$ 替换为 1

没有其他的执行序列不会让小枫生气。