Chmax Rush!

时间限制：2s
空间限制：1024MB

题目描述

有一个长度为 $N$ 的整数序列 $S$，初始时所有元素都是 $0$。另给定 $Q$ 组整数 $(P_i,V_i)$，需要按 $i=1,2,\ldots,Q$ 的顺序执行操作。

第 $i$ 次操作必须从下面两种方式中选择一种：

• 将 $S_1,S_2,\ldots,S_{P_i}$ 全部替换为 $V_i$。若替换前这段中存在严格大于 $V_i$ 的元素，则该选择失败。
• 将 $S_{P_i},S_{P_i+1},\ldots,S_N$ 全部替换为 $V_i$。若替换前这段中存在严格大于 $V_i$ 的元素，则该选择失败。

求能够顺利完成全部 $Q$ 次操作的选择序列数，对 $998244353$ 取模。只要某一次选择的方向不同，就视为不同的操作序列。

输入格式

第一行包含两个整数 $N,Q$。

接下来 $Q$ 行，第 $i$ 行包含两个整数 $P_i,V_i$。

输出格式

输出合法操作序列数对 $998244353$ 取模后的结果。

样例输入 1

8 3
1 8
8 1
2 1

样例输出 1

1

样例输入 2

8 3
8 1
1 8
1 2

样例输出 2

0

数据范围

对于所有数据，$2\le N\le5000$，$1\le Q\le5000$，$1\le P_i\le N$，$1\le V_i\le10^9$。