AT_agc028_d [AGC028D] Chords

[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/A

N/A

### 制約 - $ 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)