ストーリー

「これは…？」そこに着いた僕たちが見たものは、魔法陣のようなものだった。かすれて、ところどころ欠けていて、不完全なのは誰の目にも明らかだった。
今までの僕なら、これを直さずにここで帰っていたかもしれない。でも今は───"真実"が、知りたい。

問題文

あなたの目の前には、巨大な円が描かれています。あなたはこの円を使って、魔法陣を完成させる必要があります。
魔法陣とは、 $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

解説

解説