[AGC028D] Chords

给定一个圆, 圆上均等地放着 $2n$ 个点, 已有 $k$ 对点之间连好了线段, 从中选择剩下 $n−k$ 对点随意连线段(每个点只连一条线段). 两点联通当且仅当两点在同一条线段上或两点所属于的线段相交, 求所有连边方案中, 联通块的个数和.

[problemUrl]: https://atcoder.jp/contests/agc028/tasks/agc028_d 円周上に $ 2N $ 個の点が等間隔に並んでいます。 これらの点はある点を基準に、時計回りに $ 1 $ から $ 2N $ までの番号が付けられています。 すぬけ君は、これらの点を $ N $ 個のペアに分けて、各ペアについてペアの点対を結ぶ線分を書きます。 線分を書き終えた後で、ある $ 2 $ つの点が**連結**であるとは、一方の点からスタートし、書かれた線分上のみを移動することによって、他方の点に到達できることを意味します。 また、ここでの**連結成分の個数**は、$ 2N $ 個の点を頂点とみなし、連結な点対全てについて辺を張ったグラフにおける連結成分の個数を意味します。 すぬけ君はすでに $ K $ 個のペアを決定しており、そのうち $ i $ 番目のペアは、点 $ A_i $ と点 $ B_i $ のペアです。 すぬけ君は残りの $ N-K $ ペアの作り方を全通り試して、それら全てについて連結成分の個数を数えようとしています。 これらの連結成分の個数の総和がいくらになるかを求めてください。 ただし、答えは非常に大きくなることがあるので、$ 10^9+7 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ : $ $ A_K $ $ B_K $

残りの $ N-K $ ペアの作り方を全通り試し、それら全てについて連結成分の個数を求めた際のその総和を $ 10^9+7 $ で割った余りを出力せよ。

2 0

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

### 制約 - $ 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 $ はすべて異なる。 - 入力は全て整数である。 ### Sample Explanation 1 線分の書き方は以下の $ 3 $ 通りで、それぞれの連結成分の個数は $ 2 $, $ 2 $, $ 1 $ です。 よって答えは $ 2+2+1=5 $ になります。 !\[\](https://img.atcoder.jp/agc028/b5dcbaf5c8caf26b4e7e4915954565f7.png)