/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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