Chords

AtCoder

IDagc028_d

Time2000ms

Memory256MB

Difficulty—

There are $2N$ points evenly spaced on the circumference of a circle. These points are numbered $1$ to $2N$ in clockwise order, starting from some of them. Snuke will divide these points into $N$ pairs, then for each pair, he will draw a line segment connecting the two points. After the line segments are drawn, two points are _connected_ when one can reach from one of those points to the other by traveling only on the line segments. _The number of the connected parts_ here is the number of the connected components in the graph with $2N$ vertices, corresponding to the $2N$ points, where every pair of vertices corresponding to two connected points is connected with an edge. Snuke has already decided $K$ of the pairs, and the $i$\-th of them is a pair of Point $A_i$ and Point $B_i$. He is thinking of trying all possible ways to make the remaining $N-K$ pairs and counting the number of the connected parts for each of those ways. Find the sum of those numbers of the connected parts. As the answer can be extremely large, compute the sum modulo $10^9+7$. ## Constraints * $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$ are all distinct. * All values in input are integers. ## Input Input is given from Standard Input in the following format: $N$ $K$ $A_1$ $B_1$ $A_2$ $B_2$ $:$ $A_K$ $B_K$ [samples]

Samples

Input #1

2 0

Output #1

5

There are three ways to draw line segments, as shown below, and the number of the connected parts for these ways are $2$, $2$ and $1$, respectively. Thus, the answer is $2+2+1=5$.
![image](https://img.atcoder.jp/agc028/b5dcbaf5c8caf26b4e7e4915954565f7.png)

Input #2

4 2
5 2
6 1

Output #2

Input #3

Output #3

27087418

API Response (JSON)

{
  "problem": {
    "name": "Chords",
    "description": {
      "content": "There are $2N$ points evenly spaced on the circumference of a circle. These points are numbered $1$ to $2N$ in clockwise order, starting from some of them. Snuke will divide these points into $N$ pair",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc028_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $2N$ points evenly spaced on the circumference of a circle. These points are numbered $1$ to $2N$ in clockwise order, starting from some of them.\nSnuke will divide these points into $N$ pair...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments