Score : $650$ points

问题陈述

有一个特殊的网格，有 $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$。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

There is a special grid with $N$ rows. ($N$ is even.) The $i$-th row from the top has $\left \lceil \frac{i}{2} \right \rceil \times 2$ cells from the left end.
For example, when $N = 6$, the grid looks like the following:

Let $(i, j)$ denote the cell at the $i$-th row from the top and $j$-th column from the left.
Each cell is either an empty cell or a wall cell. There are $M$ wall cells, and the $i$-th wall cell is $(a_i, b_i)$. Here, $(1, 1)$ and $(N, N)$ are empty.
Starting from $(1, 1)$, how many ways are there to reach $(N, N)$ by repeatedly moving right or down to an adjacent empty cell? Find the count modulo $998244353$.

Constraints

• $2 \leq N \leq 2.5 \times 10^5$
• $N$ is even.
• $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)$ and $(a_i, b_i) \neq (N, N)$.
• $(a_i, b_i) \neq (a_j, b_j)$ if $i \neq j$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$

$a_1$ $b_1$

$a_2$ $b_2$

$\vdots$

$a_M$ $b_M$

Output

Print the number of ways to reach $(N, N)$ from $(1, 1)$ by repeatedly moving right or down to an adjacent empty cell, modulo $998244353$.

Sample Input 1

4 2
2 1
4 2

Sample Output 1

2

There are two paths that satisfy the conditions of the problem:

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

Sample Input 2

6 3
2 1
3 3
4 2

Sample Output 2

0

Sample Input 3

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

Sample Output 3

619611437

Sample Input 4

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

Sample Output 4

175892766