房间

题目描述

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

从建筑物的每个房间都可以移动到任意其他房间。

这里,将位于某个房间 $i$ 的人移动到另一个房间 $j$($i \neq j$)称为一次「人的移动」。

最初,建筑物的每个房间里有 $1$ 个人。

已知从那时起到现在,恰好发生了 $k$ 次人的移动。

现在,各个房间中人数可能的组合有多少种?

答案对 $(10^9 + 7)$ 取模。

输入格式

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

$n$ $k$

输出格式

输出当前各个房间人数可能的组合数对 $(10^9 + 7)$ 取模的结果。

样例

3 2

10

设现在房间 $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)$。

200000 1000000000

607923868

输出对 $(10^9 + 7)$ 取模后的结果。

15 6

22583772

数据范围

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