Segment tree is a data structure based on the divide-and-conquer algorithm, but this has nothing to do with this problem---it's just to make the title start with D.

For this problem, a segment tree is a perfect binary tree. A segment tree of depth $n$ has exactly $2^{n+1}-1$ nodes. Note that the root has depth $0$, so a segment tree of depth $n$ has $n+1$ levels.

To make the structure of a segment tree easier to describe, we assign indices to its nodes. The root is assigned index $1$. Every non-leaf node is assigned an index $k$ satisfying $1\leq k< 2^n$. It has exactly two children: its left child has index $2k$, and its right child has index $2k+1$.

Each node of a segment tree also has a value. Let $a_k$ denote the value of node $k$. For every non-leaf node $k$, its value $a_k$ must be the maximum of the values of its two children; that is, $$ a_k=\max\{a_{2k},a_{2k+1}\}. $$

The leaf nodes have indices $2^n,2^n+1,\ldots,2^{n+1}-1$, and their values must form a permutation of $1,2,\ldots,2^n$. In other words, the elements of the sequence $a_{2^n},a_{2^n+1},\ldots,a_{2^{n+1}-1}$ must be pairwise distinct integers, and $1\leq a_{2^n+i}\leq 2^n$ must hold for every $0\leq i< 2^n$.

There are now $q$ constraints. The $i$-th constraint is of the form $(u_i,x_i)$. Here, $u_i$ is a node index and $x_i$ is a specified value; the constraint requires the value $a_{u_i}$ of node $u_i$ to be equal to $x_i$. Calculate the number of segment trees satisfying all $q$ constraints, or equivalently, the number of distinct valid sequences $a_1,a_2,\ldots,a_{2^{n+1}-1}$. Output the answer modulo $998244353$.

Input

The first line contains two integers $n$ $(1\le n\le 18)$ and $q$ $(0\le q\le 2^{n+1}-1)$.

Each of the next $q$ lines contains two integers $u_i$ $(1\le u_i< 2^{n+1})$ and $x_i$ $(1\le x_i\le 2^n)$, meaning that the value $a_{u_i}$ of node $u_i$ is required to be equal to $x_i$.

Output

Output one integer: the number of valid leaf permutations modulo $998244353$.

Examples

Input 1

2 1
2 2

Output 1

4

Input 2

2 2
1 4
2 4

Output 2

12

Input 3

2 2
2 3
4 4

Output 3

0

Input 4

4 2
1 2
1 3

Output 4

0