配点 : $900$ 点

問題文

円周上に $2N$ 個の点が等間隔に並んでいます。 これらの点はある点を基準に、時計回りに $1$ から $2N$ までの番号が付けられています。

すぬけ君は、これらの点を $N$ 個のペアに分けて、各ペアについてペアの点対を結ぶ線分を書きます。 線分を書き終えた後で、ある $2$ つの点が連結であるとは、一方の点からスタートし、書かれた線分上のみを移動することによって、他方の点に到達できることを意味します。 また、ここでの連結成分の個数は、$2N$ 個の点を頂点とみなし、連結な点対全てについて辺を張ったグラフにおける連結成分の個数を意味します。

すぬけ君はすでに $K$ 個のペアを決定しており、そのうち $i$ 番目のペアは、点 $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$ ペアの作り方を全通り試し、それら全てについて連結成分の個数を求めた際のその総和を $10^9+7$ で割った余りを出力せよ。

2 0

5

線分の書き方は以下の $3$ 通りで、それぞれの連結成分の個数は $2$, $2$, $1$ です。 よって答えは $2+2+1=5$ になります。

4 2
5 2
6 1

6

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

27087418