分数: 500 点
问题陈述
有一座建筑物 n 房间,编号 1 to n.
我们可以从建筑物中的任何房间移动到任何其他房间。
让我们将以下事件称为 移动: 某个房间里的一个人 i 前往另一个房间 j~ (i \neq j).
最初,大楼的每个房间都有一个人。
之后,我们知道确切有 k 到目前为止已经发生了动作。
我们对每个区域的人数感兴趣 n 现在房间。人数的组合有多少种 n 房间可以吗?
求计数模数 (10^9 + 7).
约束
- 输入中的所有值都是整数。
- 3 \leq n \leq 2 \times 10^5
- 2 \leq k \leq 10^9
输入
输入由标准输入按以下格式给出:
n k
输出
打印出图中人数的可能组合数 n 现在房间,模数 (10^9 + 7).
示例输入 1
3 2
示例输出 1
10
让 c_1, c_2,和 c_3 是房间内的人数 现在分别是 1, 2,和 3 。有 10 的可能组合 (c_1, c_2, c_3):
- (0, 0, 3)
- (0, 1, 2)
- (0, 2, 1)
- (0, 3, 0)
- (1, 0, 2)
- (1, 1, 1)
- (1, 2, 0)
- (2, 0, 1)
- (2, 1, 0)
- (3, 0, 0)
例如, (c_1, c_2, c_3) 将是 (0, 1, 2) 如果房间里的人 1 前往房间 2 然后房间里的一个人 2 前往房间 3.
示例输入 2
200000 1000000000
示例输出 2
607923868
打印计数模数 (10^9 + 7).
示例输入 3
15 6
示例输出 3
22583772