配点 : 900 点
故事
“这是什么……?”当我们到达那里时,我们看到了类似魔法阵的东西。它有些地方已经褪色、缺失了,所有人都可以明显看出它是不完整的。
如果到现在为止,我可能没有解决这个问题就回家了。但现在……我想知道“真相”。
問題文
一个巨大的圆圈出现在你的面前。你需要使用这个法阵来完成魔法阵。
什么是魔法阵? 2N 点在圆周上等间隔排列,
它被分成N 对并绘制线段。
在圆周上 2N 点等间隔排列,从某一点开始顺时针移动。
它们的编号最大为 1 减去 2N 。
就在我面前 2N 点中,有些点已经配对并通过线段连接,但有些点尚未配对。你需要决定如何将它们配对并完成魔法圈。
当魔圈的复杂度定义为“相交成圆的线段对的数量”时,
您希望最小化所产生的魔法阵的复杂性。
找出可以最小化魔法阵复杂性的配对方式的数量,
除以10^9+7 求余数。
制約
- 所有输入均为整数
- 1 \leq N \leq 300
- 0 \leq K \leq N
- 1 \leq a_i,b_i\leq 2N (i=1,2,\dots,K)
- a_1,a_2,..,a_K,b_1,b_2,..,b_K都不同
入力
第一行,魔法阵的大小N 和已形成对的数量 K 。
继续
已组装的对在K 行中给出。
N K a_1 b_1 : a_K b_K
出力
请打印答案。
入力例 1
3 0
出力例 1
5
魔法阵的最小复杂度是0。
如何形成对以使线段不相交5方法有很多。
入力例 2
7 3 1 13 3 11 9 4
出力例 2
4
最小复杂度是2。复杂性
下面是如何组成一对来实现2形成一对来实现这一点的方法如下。4没错。
、(2,10),(5,6),(7,8),(12,14)
、(2,10),(5,8),(6,7),(12,14)
、(2,14),(5,6),(7,8),(10,12)
、(2,14),(5,8),(6,7),(10,12)
入力例 3
30 15 44 36 1 11 53 21 38 52 8 22 26 42 35 2 23 37 30 58 18 17 3 33 51 9 39 14 12 41 4 49
出力例 3
1136