得分 : $900$ 分

问题陈述

在一个圆的周长上均匀分布着 $2N$ 个点。
这些点按顺时针顺序编号为 $1$ 到 $2N$，从其中某个点开始。

Snuke 将把这些点分成 $N$ 对，然后为每对点绘制一条连接这两个点的线段。
当可以仅通过这些线段从一个点到达另一个点时，这两个点被称为 连接。
这里的 连接部分的数量 是指与 $2N$ 个顶点对应的图中的连接分量的数量，其中每一对对应于两个连接点的顶点通过一条边相连。

Snuke 已经决定了 $K$ 对，第 $i$ 对是点 $A_i$ 和点 $B_i$。

他正在考虑尝试所有可能的方法来组成剩下的 $N-K$ 对，并计算每种方法的连接部分的数量。
找出这些连接部分数量的总和。
由于答案可能极大，计算总和对 $10^9 + 7$ 取模。

约束条件

• $1 \leq N \leq 300$
• $0 \leq K \leq N$
• $1 \leq A_i,B_i \leq 2N$
• $A_1,\ A_2,\ ...\ A_K,\ B_1,\ B_2,\ ...\ B_K$ 都是不同的。
• 输入中的所有值均为整数。

输入

输入从标准输入给出，格式如下：

$N$ $K$

$A_1$ $B_1$

$A_2$ $B_2$

$:$

$A_K$ $B_K$

输出

打印所有可能的方法中剩余 $N-K$ 对的连接部分数量的总和。

2 0

5

存在三种绘制线段的方法，如下所示，这些方法的连接部分数量分别为 $2$、$2$ 和 $1$。
因此，答案是 $2+2+1=5$。

4 2
5 2
6 1

6

20 10
10 18
11 17
14 7
4 6
30 28
19 24
29 22
25 32
38 34
36 39

27087418