分数: 650 点
问题陈述
有一个特殊的网格 N 行。 (N 是偶数。) i从顶部开始的第行有
从左端开始的 \left \lceil \frac{i}{2} \right \rceil \times 2 单元格。
例如,当 N = 6,网格如下所示:

让 (i, j) 表示位于 i从顶部开始的第行和 j左起第 列。
每个单元格要么是空单元格,要么是壁单元格。有 M 壁细胞,以及 i第壁细胞是 (a_i, b_i)。在这里, (1, 1) 和 (N, N) 为空。
从 (1, 1),有多少种方式可以到达 (N, N) 通过重复向右或向下移动到相邻的空单元格?求计数模数 998244353.
约束
- 2 \leq N \leq 2.5 \times 10^5
- N 是偶数。
- 0 \leq M \leq 50
- 1 \leq a_i \leq N
- 1 \leq b_i \leq \left \lceil \frac{a_i}{2} \right \rceil \times 2
- (a_i, b_i) \neq (1, 1) 和 (a_i, b_i) \neq (N, N).
- (a_i, b_i) \neq (a_j, b_j) if i \neq j.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M a_1 b_1 a_2 b_2 \vdots a_M b_M
输出
打印到达方式的数量 (N, N) 来自 (1, 1) 通过重复向右或向下移动到相邻的空单元格,模 998244353.
示例输入 1
4 2 2 1 4 2
示例输出 1
2
满足问题条件的路径有两条:
- (1, 1) \to (1, 2) \to (2, 2) \to (3, 2) \to (3, 3) \to (3, 4) \to (4, 4)
- (1, 1) \to (1, 2) \to (2, 2) \to (3, 2) \to (3, 3) \to (4, 3) \to (4, 4)
示例输入 2
6 3 2 1 3 3 4 2
示例输出 2
0
示例输入 3
100 10 36 9 38 5 38 30 45 1 48 40 71 52 85 27 86 52 92 34 98 37
示例输出 3
619611437
示例输入 4
100000 10 552 24 4817 255 7800 954 23347 9307 28028 17652 39207 11859 48670 22013 74678 53158 75345 45891 88455 4693
示例输出 4
175892766