Not Intersect

AtCoder

IDagc065_d

Time3000ms

Memory256MB

Difficulty—

There is a circle on a plane. It has $N$ distinct points on its circumference, numbered $1,2,\dots,N$ in clockwise order. There are $\frac{N(N-1)}{2}$ line segments that can be drawn by connecting two different points among the $N$ points; you will choose and draw $M$ of these segments. Find the number, modulo $(10^9+7)$, of ways to draw $M$ segments such that no two of them intersect at a point other than their endpoints. ## Constraints * $1 \le N \le 10^7$ * $0 \le M \le \frac{N(N-1)}{2}$ ## Input The input is given from Standard Input in the following format: $N$ $M$ [samples]

Samples

Input #1

4 2

Output #1

14

The following examples on the left and in the middle satisfy the conditions. (Note that it is acceptable for the segments to intersect at their endpoints.)
The example on the right is unsuitable because two edges intersect at a point other than their endpoints. All other $\binom{6}{2} - 1 = 14$ ways satisfy the conditions.
![image](https://img.atcoder.jp/agc065/4854b47261fd9c54c2d25ee53c3e6be5.png)

Input #2

6 3

Output #2

Input #3

2023 1217

Output #3

10811951

Input #4

1234321 2345432

Output #4

789452255

API Response (JSON)

{
  "problem": {
    "name": "Not Intersect",
    "description": {
      "content": "There is a circle on a plane. It has $N$ distinct points on its circumference, numbered $1,2,\\dots,N$ in clockwise order. There are $\\frac{N(N-1)}{2}$ line segments that can be drawn by connecting two",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc065_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is a circle on a plane. It has $N$ distinct points on its circumference, numbered $1,2,\\dots,N$ in clockwise order.\nThere are $\\frac{N(N-1)}{2}$ line segments that can be drawn by connecting two...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments