Number of good permutations

You are given two arrays $X$ and $V$ of size $M$ and an integer $N$. Write a program that counts the permutations $P$ of length $N$ that satisfy all three conditions below. Arrays and permutations are numbered from 1.

• $P$ is a sequence in which each of the numbers 1 through $N$ appears exactly once.
• At least one pair $(i, j)$ satisfies $i < j$, $P[i] > j$ and $P[j] > i$.
• $P[X[i]] = V[i]$ holds for every $1 \le i \le M$.

The same value appears in $X$ more than once in some inputs. If no permutation meets all three conditions, the answer is 0.

The first line contains the number of test cases $T$ ($1 \le T \le 10$).

The first line of each test case contains $N$ and $M$ ($1 \le N \le 10^9$, $0 \le M \le 10^4$). The $i$-th of the next $M$ lines contains $X[i]$ and $V[i]$ ($1 \le X[i], V[i] \le N$).

For each test case, print the number of permutations $P$ that satisfy the conditions, modulo $2000000011$, on its own line.

For $N = 3$ with no fixed value, $(3, 2, 1)$ is the only permutation that satisfies the conditions.