Maximin Permutation Count with Fixed Positions

You are given an integer N (2 ≤ N ≤ 2000) and K restrictions of the form p[i] = j (0 ≤ i, j < N). Consider all permutations p = [p₀, p₁, …, p_N-1] of the set {0, 1, …, N−1}.

For a permutation p, define

Let S be the set of permutations for which f(p) is maximized – that is, f(p) attains its maximum possible value. It can be shown that the maximum possible value is $$\lfloor \frac{N}{2}\rfloor.$$

It turns out that when N is even the optimal permutation is unique up to reversal (exactly 2 solutions) and when N is odd there are exactly 6 optimal permutations (for N = 3 the 6 permutations are all optimal, and for N ≥ 5 the 6 solutions are characterized by a very rigid structure).

Your task is to count how many permutations in S satisfy all the given restrictions. Since the answer can be very large, output it modulo 109+7.

Note: The time limit stated in the problem is 4 seconds (usually two times the typical 2‐second limit).

inputFormat

The first line contains two integers N and K.

The following K lines each contain two integers i and j, indicating the restriction p[i] = j.

outputFormat

Output one integer, the number of optimal permutations that satisfy all the given restrictions, taken modulo 109+7.

sample

3 0

6