좋은 순열의 개수

크기가 $M$인 배열 $X$와 $V$, 그리고 정수 $N$이 주어진다. 다음 세 조건을 모두 만족하는 길이 $N$짜리 순열 $P$의 개수를 구하는 프로그램을 작성하시오. 배열과 순열의 번호는 모두 1번부터 매긴다.

• $P$는 1부터 $N$까지의 수가 각각 한 번씩 나오는 수열이다.
• $i < j$이면서 $P[i] > j$이고 $P[j] > i$인 쌍 $(i, j)$가 적어도 하나 있다.
• 모든 $1 \le i \le M$에 대해 $P[X[i]] = V[i]$이다.

$X$에는 같은 값이 여러 번 나오기도 한다. 세 조건을 동시에 만족하는 순열이 하나도 없으면 답은 0이다.

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

각 테스트 케이스의 첫째 줄에는 $N$과 $M$($1 \le N \le 10^9$, $0 \le M \le 10^4$)이 주어진다. 이어지는 $M$개 줄 가운데 $i$번째 줄에는 $X[i]$와 $V[i]$($1 \le X[i], V[i] \le N$)가 주어진다.

각 테스트 케이스마다 조건을 만족하는 순열 $P$의 개수를 $2000000011$로 나눈 나머지를 한 줄에 출력한다.

$N = 3$이고 고정된 값이 하나도 없으면 조건을 만족하는 순열은 $(3, 2, 1)$ 하나뿐이다.