题目描述

There is a building with $n$ rooms, numbered $1$ to $n$.

We can move from any room to any other room in the building.

Let us call the following event a move: a person in some room $i$ goes to another room $j~ (i \neq j)$.

Initially, there was one person in each room in the building.

After that, we know that there were exactly $k$ moves happened up to now.

We are interested in the number of people in each of the $n$ rooms now. How many combinations of numbers of people in the $n$ rooms are possible?

Find the count mod $(10^9 + 7)$.

有一栋楼，有 $n$ 个房间，编号为 $1$ 至 $n$ 。

我们可以从任何房间移动到大楼里的任何其他房间。

我们把下面的事件称为移动：某个房间 $i$ 里的人去了另一个房间 $j~ (i \neq j)$ 。

最初，大楼里每个房间都有一个人。

从那以后，我们知道到现在为止一共发生了 $k$ 次移动。

我们现在感兴趣的是 $n$ 个房间里的人数。 $n$ 个房间的人数可能有多少种组合？

求模数 $(10^9 + 7)$ 。

输入格式

输入内容按以下格式标准输入：

$n$ $k$

输出格式

打印现在 $n$ 房间人数的可能组合数，模数为 $(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$ 解释

设 $c_1$ 、 $c_2$ 和 $c_3$ 分别是现在 $1$ 、 $2$ 和 $3$ 房间的人数。 $(c_1, c_2, c_3)$ 有 $10$ 种可能的组合：

• $(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)$ 。

样例 $2$ 解释

打印计数 mod $(10^9 + 7)$ 。