103576: [Atcoder]ABC357 G - Stair-like Grid

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

问题描述

有一个特殊的网格，有$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)$。
• 如果$i \neq j$，则$(a_i, b_i) \neq (a_j, b_j)$。
• 所有输入值都是整数。

输入

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

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

输出

打印从$(1, 1)$到$(N, N)$反复向右或向下移动到相邻空单元格的路径数，以$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