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.

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.

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.

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

见题面 Input 部分

见题面 Output 部分