Dishonest Paths

You are given an integer $N$ and the following undirected graph:

• The graph contains $N$ nodes, which are numbered from $1$ to $N$.
• There exists an undirected edge between two nodes $U$ and $V$ ($1 \le U,V \le N$) if and only if $1 \le |U-V| \le 2$.

There are $M$ distinct forbidden edges $(U_i,V_i)$ ($i = 0, \ldots, M - 1$).

Task

Find the number of simple paths in this graph from node $1$ to node $N$ that do not contain any of the $M$ forbidden edges. Since the answer can be very large, print its remainder modulo $998 \ 244 \ 353$.

A simple path is a sequence of \textbf{pairwise distinct} nodes $u_1,u_2,\ldots,u_k$ such that $u_i$ and $u_{i+1}$ are connected by an edge in the graph, for all $1 \le i < k$.

Input data

The first line of input contains two integers $N$ and $M$ -- the number of nodes in the graph, and the number of forbidden edges, respectively.

Each of the next $M$ lines of input contains two integers $U_i$ and $V_i$ -- the endpoints of the forbidden edges.

Output data

Print the number of simple paths (modulo $998 \ 244 \ 353$) from node $1$ to node $N$ that do not contain any of the $M$ forbidden edges.

Constraints and clarifications

• $3 \le N \le 10^{18}$.
• $0 \le M \le \min(2 \cdot N - 3, 100 \ 000)$.
• $1 \le U_i < V_i \le N$, $1 \le V_i - U_i \le 2$ for each $i=0\ldots M-1$.
• The edges $(U_i, V_i)$ are pairwise distinct.

Example 1

stdin

5 0

stdout

7

Explanation

In the first sample case, there are $7$ simple paths from node $1$ to node $5$:

• $1 \rightarrow 2 \rightarrow 4 \rightarrow 3 \rightarrow 5$
• $1 \rightarrow 2 \rightarrow 4 \rightarrow 5$
• $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$
• $1 \rightarrow 2 \rightarrow 3 \rightarrow 5$
• $1 \rightarrow 3 \rightarrow 2 \rightarrow 4 \rightarrow 5$
• $1 \rightarrow 3 \rightarrow 5$
• $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$

Example 2

stdin

5 1
3 4

stdout

4

Explanation

In the second sample case, there are $4$ simple paths from node $1$ to node $5$ that do not contain the edge $(3,4)$:

• $1 \rightarrow 2 \rightarrow 4 \rightarrow 5$
• $1 \rightarrow 2 \rightarrow 3 \rightarrow 5$
• $1 \rightarrow 3 \rightarrow 2 \rightarrow 4 \rightarrow 5$
• $1 \rightarrow 3 \rightarrow 5$

Example 3

stdin

3 2
1 2
1 3

stdout

0

Explanation

In the third sample case, there are no simple paths from node $1$ to node $3$ that do not contain the edges $(1,2)$ and $(1,3)$.

Example 4

stdin

8 6
4 5
6 7
6 8
1 2
2 3
2 4

stdout

2

Explanation

In the fourth sample case, there are only two valid simple paths from node $1$ to node $8$:

• $1 \rightarrow 3 \rightarrow 4 \rightarrow 6 \rightarrow 5 \rightarrow 8$
• $1 \rightarrow 3 \rightarrow 5 \rightarrow 7 \rightarrow 8$

Example 5

stdin

100 8
1 2
98 100
54 55
20 22
80 81
80 82
83 84
82 84

stdout

249047307

Example 6

stdin

2000000000 0

stdout

548668789