Consider a permutation $p=(p_1, p_2, \cdots, p_N)$ of length $N$. That is, $p$ is a sequence in which each integer from $1$ to $N$ appears exactly once.

This permutation $p$ must satisfy all of the $M$ conditions given in advance. Each condition is specified for a particular position $i$ and is one of the following two forms:

• $p_i > i$
• $p_i < i$

Let $S$ be the set of all permutations of length $N$ that satisfy all $M$ conditions.

Now, to measure the cost of sorting each permutation $p \in S$ in ascending order, we define the following two operations:

• Operation 1: Choose an index $i$ with $1 \le i < N$ and swap $p_i$ and $p_{i+1}$.
• Operation 2: Choose indices $i, j$ with $1 \le i < j \le N$ and swap $p_i$ and $p_j$.

For some permutation $p$, let $f(p)$ be the minimum number of operations required to sort $p$ in ascending order using only Operation 1, and let $g(p)$ be the minimum number of operations required to sort $p$ in ascending order using only Operation 2.

Your goal is to compute, for all permutations $p \in S$, the sum of the product $f(p) \cdot g(p)$. Compute the value of

$$ \sum_{p\in S} f(p) \cdot g(p) $$

modulo $998\,244\,353$.

Input

The first line contains two space-separated integers $N$ and $M$.

Each line of the following $M$ lines contains two space-separated integers $t$ and $i$, which mean the following:

• If $t = 1$, $p_i > i$
• If $t = 2$, $p_i < i$

Output

Print $\sum_{p \in S} f(p) \cdot g(p)$ modulo $998\, 244\, 353$.

Constraints

• $2 \le N \le 3000$
• $0 \le M \le N$
• $t \in \{1,2 \}$
• $1 \le i \le N$
• For each index $i$, at most one condition is given.

Scoring

Examples

Input 1

3 1
2 3

Output 1

12

Input 2

3 1
1 3

Output 2

0

Input 3

6 3
1 3
2 4
1 5

Output 3

938

Note

In Example 1, $S = \{(1,3,2),(2,3,1),(3,1,2),(3,2,1)\}$. The $f$ and $g$ values for each permutation are as follows.

• $f((1,3,2)) = 1$, $g((1,3,2))=1$
• $f((2,3,1)) = 2$, $g((2,3,1))=2$
• $f((3,1,2)) = 2$, $g((3,1,2))=2$
• $f((3,2,1)) = 3$, $g((3,2,1))=1$

Print $1\times 1 + 2\times 2 + 2\times 2 + 3\times 1 = 12$.

In Example 2, no permutation satisfies the conditions. Therefore, print $0$.