← 返回题目列表

AtCoder · agc065_d

D. 不相交

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

平面上有一个圆。它有 N 圆周上的不同点,已编号 1,2,\dots,N 按顺时针顺序。

有 \frac{N(N-1)}{2} 可以通过连接两个不同点来绘制的线段 N 点;你将选择并绘制 这些段的 M 。求模数 (10^9+7),绘制方法 M 段,使得它们中没有两个在除端点以外的点相交。

约束

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

输入

输入由标准输入按以下格式给出:

N M

输出

打印答案。


示例输入 1

4 2

示例输出 1

14

以下左侧和中间的示例满足条件。 (请注意,线段在端点处相交是可以接受的。)

右侧的示例不合适,因为两条边相交的点不是其端点。所有其他 \binom{6}{2} - 1 = 14 方式满足条件。


示例输入 2

6 3

示例输出 2

295

示例输入 3

2023 1217

示例输出 3

10811951

示例输入 4

1234321 2345432

示例输出 4

789452255