33618번 - 내 맘대로 정렬

평소에 다른 사람이 만든 정렬 문제만 풀던 피돌이는 이제 문제 풀이에 질렸다! 그래서 피돌이는 버블 정렬의 과정에서 아이디어를 얻어온 인접 요소 교환을 통해 자신이 정한 $Q$개의 소원을 만족하는 길이가 $N$인 순열 $A=[a_1, a_2, \cdots, a_N]$를 찾는 문제를 만들기로 했다. 길이가 $N$인 순열이란 $1$부터 $N$까지의 정수가 한 번씩 등장하는 수열을 말한다.

인접 요소 교환이란, 다음 행동을 순차적으로 한 번 수행하는 것을 말한다.

• $a_1$과 $a_2$를 비교하여 $a_2$가 더 크면 그대로 두고 더 작으면 둘의 위치를 바꾼다.
• $a_2$와 $a_3$을 비교하여 $a_3$이 더 크면 그대로 두고 더 작으면 둘의 위치를 바꾼다.
• $\cdots$
• $a_{N-1}$과 $a_N$을 비교하여 $a_N$이 더 크면 그대로 두고 더 작으면 둘의 위치를 바꾼다.

즉, 한 번의 인접 요소 교환에서 $N-1$번의 비교와 위치 교환 시도가 일어난다. 예를 들어, $[2, 3, 1]$에 인접 요소 교환을 한 번 한 경우, $[2, 1, 3]$이 된다.

피돌이가 만든 문제의 순열 $A$는 $Q$개의 소원을 모두 만족해야 한다. $i$번째 소원은 두 정수 $p_i$와 $q_i$로 나타내며, 이는 $A$에 인접 요소 교환을 한 번 한 후의 $a_{q_i}$값이 인접 요소 교환 전의 $a_{p_i}$ 값과 같아야 한다는 뜻이다.

피돌이는 $A$로 가능한 순열을 모두 구해보고 싶었지만 너무 많다 생각하여 개수만 구하기로 하였다. 단, 개수가 너무 커질 수 있으므로 개수를 $1\,000\,000\,007$로 나눈 나머지를 구해보자.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $\ (1\le T\le 200\ 000)$

각 테스트 케이스의 첫째 줄에 순열의 길이 $N$이 주어진다. $\ (2\le N\le 500\ 000)$

각 테스트 케이스의 둘째 줄에 소원의 개수 $Q$가 주어진다. $\ (1\le Q\le 200\ 000)$

각 테스트 케이스의 다음 $Q$줄에 정수 $p_i, q_i$가 공백을 두고 주어진다. $(1\le p_i\le q_i\le N)$

주어지는 모든 소원은 다름이 보장된다. 즉 $i\ne j$이면 $(p_i,\ q_i)\ne (p_j,\ q_j)$이다.

모든 테스트 케이스에서 $Q$의 합은 $200\ 000$을 넘지 않는다.

각 테스트 케이스의 첫째 줄에 가능한 순열 $A$의 개수를 $1\ 000\ 000\ 007$로 나눈 나머지를 출력한다.

모든 테스트 케이스의 $N$의 합에는 제한이 없음에 유의해라.