集合 $M$ 的一个排列 $p$ 被称为对合（involution），如果对于每个 $i \in M$ 都有 $p(p(i)) = i$。

长度为 $2n$ 的括号序列是指一个仅由字符 '(' 和 ')' 组成的长度为 $2n$ 的字符串。如果一个括号序列中左括号的数量等于右括号的数量，且对于该序列的任意前缀，左括号的数量都不小于右括号的数量，则称该括号序列是合法的。

如果一个长度为 $2n$ 的排列 $p$ 编码了一个长度为 $2n$ 的括号序列，我们称其为编码，其中该序列的左括号（从左到右）位于位置 $p(1), p(2), \ldots, p(n)$，右括号（从左到右）位于位置 $p(n+1), p(n+2), \ldots, p(2n)$。特别地，在这种情况下，满足 $p(1) < p(2) < \ldots < p(n)$ 且 $p(n+1) < p(n+2) < \ldots < p(2n)$。

已知排列 $p$ 在某些参数下的取值。需要确定有多少种方式可以补全 $p$ 的剩余值，使得 $p$ 既是一个对合，又编码了一个合法的括号序列。

注：集合 $M = \{1, 2, 3, \ldots, m\}$ 的排列是任意一一映射函数 $p : M \to M$。

输入格式

标准输入的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 1\,000\,000$，$1 \le k \le 2n$），由一个空格分隔。接下来的 $k$ 行，每行包含一对由空格分隔的整数；其中第 $i$ 行包含数字 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le 2n$），表示 $p(a_i) = b_i$。所有 $a_i$ 的值互不相同，所有 $b_i$ 的值互不相同。

输出格式

标准输出的第一行且仅包含一行，输出一个整数：满足以下条件的集合 $\{1, 2, 3, \ldots, 2n\}$ 的排列数量：该排列是对合，编码了一个合法的括号序列，且对于每个 $1 \le i \le k$ 满足 $p(a_i) = b_i$。

样例

样例输入 1

3 4
1 1
2 2
4 3
6 6

样例输出 1

1

唯一符合题目要求的排列是 <1, 2, 4, 3, 5, 6>，它编码了如下括号序列：(()())。