阶梯形网格

题目描述

有一个特殊的 $N$ 行网格（$N$ 是偶数）。从上数第 $i$ 行有从左端起 $\left \lceil \frac{i}{2} \right \rceil \times 2$ 个格子。

例如，当 $N = 6$ 时，网格如下（第 1、2 行各 2 格，第 3、4 行各 4 格，第 5、6 行各 6 格）。

用 $(i, j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的格子。

每个格子要么是空格，要么是墙格。共有 $M$ 个墙格，第 $i$ 个墙格是 $(a_i, b_i)$。这里，$(1, 1)$ 和 $(N, N)$ 是空格。

从 $(1, 1)$ 出发，只能向右或向下移动到相邻的空格，问到达 $(N, N)$ 的路径有多少条？求方案数除以 $998244353$ 的余数。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_M$ $b_M$

输出格式

输出从 $(1, 1)$ 出发，只能向右或向下移动到相邻的空格，到达 $(N, N)$ 的路径方案数除以 $998244353$ 的余数。

样例

4 2
2 1
4 2

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)$

6 3
2 1
3 3
4 2

0

100 10
36 9
38 5
38 30
45 1
48 40
71 52
85 27
86 52
92 34
98 37

619611437

100000 10
552 24
4817 255
7800 954
23347 9307
28028 17652
39207 11859
48670 22013
74678 53158
75345 45891
88455 4693

175892766

数据范围

• $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)$
• 若 $i \neq j$，则 $(a_i, b_i) \neq (a_j, b_j)$
• 输入均为整数