← 返回题目列表

AtCoder · agc028_d

D. 和弦

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

有 2N 点在圆周上均匀分布。 这些点已编号 1 to 2N 按顺时针顺序,从其中一些开始。

Snuke 会将这些点分为 N 对,然后对于每一对,他将画一条连接两点的线段。 绘制线段后,有两个点 已连接 当一个人可以通过仅在线段上行进从其中一个点到达另一点时。 连接部件的数量 这里是图中连通分量的数量 2N 顶点,对应于 2N 点,其中对应于两个连接点的每对顶点都与一条边连接。

Snuke已经决定了 K 的对,以及 i- 其中第一个是一对 Point 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 对。


示例输入 1

2 0

示例输出 1

5

绘制线段有三种方式,如下所示,这三种方式的相连部分的数量为 分别是 2, 2 和 1。 因此,答案是 2+2+1=5.


示例输入 2

4 2
5 2
6 1

示例输出 2

6

示例输入 3

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

示例输出 3

27087418