题目描述

在圆周上有 $2N$ 个点等间隔排列。这些点以某一点为基准，按顺时针方向依次编号为 $1$ 到 $2N$。

すぬけ君要将这些点分成 $N$ 对，对于每一对点，画一条连接这两个点的线段。画完所有线段后，若从某一个点出发，仅沿着已画的线段移动能够到达另一个点，则称这两个点是连通的。此外，这里的连通分量的个数，指的是以这 $2N$ 个点为顶点、对所有连通点对连一条边所构成的图中的连通分量个数。

すぬけ君已经确定了 $K$ 对点，其中第 $i$ 对为点 $A_i$ 和点 $B_i$。

现在，すぬけ君要尝试所有剩余 $N-K$ 对点的配对方式，并对每一种配对方式，统计连通分量的个数。请你求出所有配对方式下连通分量个数的总和。由于答案可能非常大，请输出对 $10^9+7$ 取模的结果。

输入格式

输入以如下格式从标准输入读入。

$N$ $K$ $A_1$ $B_1$ $A_2$ $B_2$ $\cdots$ $A_K$ $B_K$

输出格式

请输出尝试所有剩余 $N-K$ 对点的配对方式后，所有情况下连通分量个数的总和对 $10^9+7$ 取模的结果。

样例 1

输入

2 0

输出

5

样例 2

输入

4 2
5 2
6 1

输出

6

样例 3

输入

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

输出

27087418

说明/提示

限制条件

• $1 \leq N \leq 300$
• $0 \leq K \leq N$
• $1 \leq A_i, B_i \leq 2N$
• $A_1, A_2, \ldots, A_K, B_1, B_2, \ldots, B_K$ 均互不相同。
• 所有输入均为整数。

样例解释 1

线段的画法有以下 $3$ 种，每种情况下的连通分量个数分别为 $2$、$2$、$1$。因此答案为 $2+2+1=5$。

由 ChatGPT 4.1 翻译