Problem Statement

There are $N$ cells numbered from $1$ to $N$. Initially, no cell is painted with any color.

There are $M$ types of colors, and with the $i$-th color, you can paint any number of cells you like among cells $L_i,L_i+1,\ldots,R_i$.

Find the number, modulo $998244353$, of ways to paint the cells that satisfy the following condition:

• For every cell $i$, if that cell is painted with a color, then exactly one of cells $i-1$ and $i+1$ is painted with the same color as cell $i$.
• Here, cells $0$ and $N+1$ are considered to be not painted with any color.

Constraints

• $1\leq N,M \leq 5\times 10^5$
• $1\leq L_i \leq R_i \leq N$
• All input values are integers.

Input

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

N M
L_1 R_1
\vdots
L_M R_M

Output

Output the answer.