순열

집합 $M = \{1, 2, 3, \dots, m\}$ 위의 순열 $p$란 일대일 대응 $p : M \to M$을 뜻한다. 순열 $p$가 모든 $i \in M$에 대해 $p(p(i)) = i$를 만족하면 $p$를 대합(involution)이라고 부른다.

길이가 $2n$인 괄호 표현식이란 문자 (와 )만으로 이루어진 길이 $2n$짜리 문자열이다. 괄호 표현식이 올바르다(correct)는 것은, 여는 괄호 (의 개수와 닫는 괄호 )의 개수가 같고, 문자열의 모든 접두사에서 (의 개수가 )의 개수보다 작지 않다는 뜻이다.

순열 $p$가 길이 $2n$인 괄호 표현식을 부호화한다(encode)는 것은 다음을 뜻한다. 여는 괄호들은 왼쪽에서 오른쪽 순서로 위치 $p(1), p(2), \dots, p(n)$에 있고, 닫는 괄호들도 왼쪽에서 오른쪽 순서로 위치 $p(n+1), p(n+2), \dots, p(2n)$에 있다. 특히 이 경우 $p(1) < p(2) < \dots < p(n)$과 $p(n+1) < p(n+2) < \dots < p(2n)$이 모두 성립한다.

$p$의 값 중 일부가 이미 주어져 있다. 남은 값들을 채워서 $p$가 대합이면서 어떤 올바른 괄호 표현식을 부호화하도록 만드는 방법의 수를 구하여라.

표준 입력의 첫 줄에는 공백으로 구분된 두 정수 $n$과 $k$가 주어진다 ($1 \le n \le 10^6$, $1 \le k \le 2n$). 이어지는 $k$개의 줄에는 각각 공백으로 구분된 정수 쌍이 주어진다. 그중 $i$번째 줄에는 $p(a_i) = b_i$임을 뜻하는 두 정수 $a_i$와 $b_i$가 있다 ($1 \le a_i, b_i \le 2n$). 모든 $a_i$는 서로 다르고, 모든 $b_i$도 서로 다르다.

집합 $\{1, 2, 3, \dots, 2n\}$의 순열 중에서 대합이고, 어떤 올바른 괄호 표현식을 부호화하며, 모든 $1 \le i \le k$에 대해 $p(a_i) = b_i$를 만족하는 순열의 개수를 한 줄에 정수 하나로 출력한다.

첫 번째 예제에서 모든 조건을 만족하는 순열은 $p = \langle 1, 2, 4, 3, 5, 6 \rangle$ 하나뿐이며, 이 순열은 괄호 표현식 (()())를 부호화한다.