A permutation^{1} $p$ of a set $m$ is called an involution if $p(p(i)) = i$ for each $i ∈ M$.

By a bracket expression of length $2n$ we mean a word of length $2n$ consisting only of the characters '(' and ')'. A bracket expression is called correct if the number of opening brackets in the expression equals the number of closing brackets and in every prefix of the expression the number of the characters '(' is no less than the number of characters ')'.

We say that a permutation $p$ of length $2n$ encodes a bracket expression of length $2n$, if opening brackets of the expression (from left to right) are located at positions $p(1), p(2), \ldots, p(n)$, and closing brackets - also from left to right - at positions $p(n+1), p(n+2), \ldots, p(2n)$. In particular, in such a case both $p(1) < p(2) < \ldots < p(n)$ and $p(n+1) < p(n+2) < \ldots < p(2n)$ hold.

The values of a permutation $p$ for several arguments are known. It should be determined in how many ways the remaining values of p can be determined in such a way that it is an involution and it encodes a correct bracket expression.

^{1}. A permutation of a set $M = \{1, 2, 3, \ldots, m\}$ is any one-to-one function $p : M → M$.

Input Format

The first line of the standard input contains two integers $n$ and $k$ ($1 ≤ n ≤ 1\,000\,000$, $1 ≤ k ≤ 2n$) separated by a single space. Each of the following $k$ lines contains one pair of space-separated integers; the $i^{\text{th}}$ of these lines contains numbers $a_{i}$ and $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ 2n$), meaning that $p(a_{i}) = b_{i}$. All values $a_{i}$ are distinct and all values $b_{i}$ are distinct.

Output Format

The first and only line of the standard output should contain a single integer: the number of permutations of the set $\{1, 2, 3, \ldots, 2n\}$ that: are involutions, encode some correct bracket expression, and for which $p(a_{i}) = b_{i}$ holds for each $1 ≤ i ≤ k$.

Example

Input

3 4
1 1
2 2
4 3
6 6

Output

1

The only permutation that complies with requirements of the task is <1, 2, 4, 3, 5, 6>, and it encodes the following bracket expression: (()()).