题目描述

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

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

输入格式

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

$N$ $M$

输出格式

输出答案。

样例 1

输入

4 2

输出

14

样例 2

输入

6 3

输出

295

样例 3

输入

2023 1217

输出

10811951

样例 4

输入

1234321 2345432

输出

789452255

说明/提示

限制条件

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

样例解释 1

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

由 ChatGPT 4.1 翻译