E - 漫游

分数：500 分

问题描述

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

我们可以从建筑中的任意一个房间移动到任意另一个房间。

我们称以下事件为一次移动：一个人从某个房间 $i$ 前往另一个房间 $j~ (i \neq j)$。

最初，建筑中的每个房间都有一个人。

然后，我们知道到目前为止一共发生了 $k$ 次移动。

我们对现在每个房间中的人数感兴趣。有多少种可能的房间人数组合？

将计数对 $(10^9 + 7)$ 取模。

约束

• 输入中的所有值都是整数。
• $3 \leq n \leq 2 \times 10^5$
• $2 \leq k \leq 10^9$

输入

从标准输入读入输入数据，数据格式如下：

$n$ $k$

输出

打印可能的房间人数组合数，对 $(10^9 + 7)$ 取模。

3 2

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)$

例如，如果房间 $1$ 中的人前往房间 $2$，然后房间 $2$ 中的其中一个人前往房间 $3$，则 $(c_1, c_2, c_3)$ 将是 $(0, 1, 2)$。

200000 1000000000

607923868

对 $(10^9 + 7)$ 取模后打印计数结果。

15 6

22583772