AT_abc357_g [ABC357G] Stair-like Grid

有一个特殊形状的纵向 $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$ 取模后输出。

输入以如下格式从标准输入读入。 > $N$ $M$ $a_1$ $b_1$ $a_2$ $b_2$ $\vdots$ $a_M$ $b_M$

输出从 $(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)$ - 若 $i \neq j$，则 $(a_i, b_i) \neq (a_j, b_j)$ - 所有输入均为整数 ## 样例解释 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)$ 由 ChatGPT 4.1 翻译