/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
ある平面上に円周が書かれています。この円周上には N 個の相異なる点があり、それらには時計回りに 1,2,\dots,N と番号が付いています。
N 個の点のうち異なる 2 点を結ぶような線分は \frac{N(N-1)}{2} 本ありますが、このうち M 本を選んで書きます。どの 2 本の線分も端点以外では交わらないような方法の個数を 10^9+7 で割ったあまりを求めてください。
制約
- 1 \le N \le 10^7
- 0 \le M \le \frac{N(N-1)}{2}
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
答えを出力せよ。
入力例 1
4 2
出力例 1
14
左、真ん中の例は条件を満たしています。(端点では交わってもいいことに注意してください。)
右の例は、2 本の辺が端点以外で交わっているため不適です。この例以外の \binom{6}{2} - 1 = 14 通りは全て条件を満たします。
入力例 2
6 3
出力例 2
295
入力例 3
2023 1217
出力例 3
10811951
入力例 4
1234321 2345432
出力例 4
789452255
Score : 900 points
Problem Statement
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
Output
Print the answer.
Sample Input 1
4 2
Sample 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.
Sample Input 2
6 3
Sample Output 2
295
Sample Input 3
2023 1217
Sample Output 3
10811951
Sample Input 4
1234321 2345432
Sample Output 4
789452255