AT_agc065_d.[AGC065D] Not Intersect

在一个平面上画有一个圆周。圆周上有 $N$ 个不同的点，这些点按顺时针方向依次编号为 $1,2,\dots,N$。

在这 $N$ 个点中，任意两点之间可以连一条线段，共有 $\frac{N(N-1)}{2}$ 条不同的线段。现在从中选出 $M$ 条线段画出来。请计算有多少种选法，使得任意两条线段除了端点外不会相交。请将答案对 $10^9+7$ 取模后输出。

输入以如下格式从标准输入读入。

$N$ $M$

输出答案。

限制条件

• $1 \leq N \leq 10^7$
• $0 \leq M \leq \frac{N(N-1)}{2}$

样例解释 1

左侧和中间的例子满足条件。（注意，线段在端点处相交是允许的。）右侧的例子不满足条件，因为有两条边在端点以外的地方相交。除此之外，剩下的 $\binom{6}{2} - 1 = 14$ 种情况都满足条件。

由 ChatGPT 4.1 翻译