← 返回题目列表

AtCoder · abc156_e

E. 漫游

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

分数: 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