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