Roaming

题目描述

有一栋楼共有 $n$ 个房间，编号为 $1$ 到 $n$。 我们可以从任意房间移动到楼内的任意其他房间。 我们将以下事件称为一次 移动：某个房间 $i$ 的一个人前往另一个房间 $j~ (i \neq j)$。 最初，楼内每个房间各有一个人。 之后，我们知道到目前为止恰好发生了 $k$ 次移动。 我们关注现在 $n$ 个房间中每个房间的人数。有多少种可能的 $n$ 个房间人数的组合？ 求该数量对 $(10^9 + 7)$ 取模的结果。

输入格式

输入从标准输入按照以下格式给出： $n$ $k$

输出格式

输出现在 $n$ 个房间中人数可能的组合数，对 $(10^9 + 7)$ 取模。

3 2

10

200000 1000000000

607923868

15 6

22583772

提示

输入中的所有数值均为整数。 $3 \leq n \leq 2 \times 10^5$ $2 \leq k \leq 10^9$设 $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)$

例如，如果房间 $1$ 的人先去房间 $2$，然后房间 $2$ 的某个人去房间 $3$，则 $(c_1, c_2, c_3)$ 为 $(0, 1, 2)$。
输出对 $(10^9 + 7)$ 取模的计数。

标签: AtCoder|abc156E

来源

AtCoder|abc156E