AT_abc156_e [ABC156E] Roaming

题目描述

有一栋有 $n$ 个房间的建筑。每个房间编号为 $1$ 到 $n$。

从建筑的任意一个房间，可以移动到其他任意房间。

这里，将某个人从房间 $i$ 移动到另一个房间 $j\ (i\neq j)$ 的操作称为人的移动。

最开始，每个房间里都有 $1$ 个人。

之后，直到现在为止，已经恰好发生了 $k$ 次人的移动。

现在，问目前每个房间里人数的所有可能的组合有多少种。

请输出方案数对 $10^9+7$ 取模的结果。

输入格式

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

$n$ $k$

输出格式

请输出目前每个房间里人数的所有可能组合的个数，对 $10^9+7$ 取模。

输入输出样例 #1

输入 #1

3 2

输出 #1

10

输入输出样例 #2

输入 #2

200000 1000000000

输出 #2

607923868

输入输出样例 #3

输入 #3

15 6

输出 #3

22583772

说明/提示

限制条件

• 所有输入均为整数。
• $3\leq n\leq 2\times 10^5$
• $2\leq k\leq 10^9$

样例解释 1

现在，设房间 $1$ 的人数为 $c_1$，房间 $2$ 的人数为 $c_2$，房间 $3$ 的人数为 $c_3$，则所有可能的 $(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)$

共 $10$ 种。例如，首先房间 $1$ 的人移动到房间 $2$，然后房间 $2$ 的某个人移动到房间 $3$，此时 $(c_1, c_2, c_3) = (0, 1, 2)$。

样例解释 2

请输出方案数对 $10^9+7$ 取模的结果。

由 ChatGPT 4.1 翻译