Problem Statement

There is an integer sequence $S$ of length $N$. Initially, all elements of $S$ are $0$.

You are also given two integer sequences of length $Q$: $P=(P_1,P_2,\dots,P_Q)$ and $V=(V_1,V_2,\dots,V_Q)$.

Snuke wants to perform $Q$ operations on the sequence $S$ in order. The $i$-th operation is as follows:

• Perform one of the following:
• Replace each of the elements $S_1, S_2, \dots, S_{P_i}$ with $V_i$. However, before this operation, if there is an element among $S_1, S_2, \dots, S_{P_i}$ that is strictly greater than $V_i$, Snuke will start crying.
  • Replace each of the elements $S_{P_i}, S_{P_i+1}, \dots, S_N$ with $V_i$. However, before this operation, if there is an element among $S_{P_i}, S_{P_i+1}, \dots, S_N$ that is strictly greater than $V_i$, Snuke will start crying.

Find the number of sequences of $Q$ operations where Snuke can perform all operations without crying, modulo $998244353$.

Two sequences of operations are distinguished if and only if there is $1 \leq i \leq Q$ such that the choice for the $i$-th operation is different.

Constraints

• $2 \leq N \leq 5000$
• $1 \leq Q \leq 5000$
• $1 \leq P_i \leq N$
• $1 \leq V_i \leq 10^9$
• All input values are integers.

Input

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

N Q
P_1 V_1
P_2 V_2
\vdots
P_Q V_Q

Output

Print the answer as an integer.