Score : $500$ points

问题陈述

存在一座包含 $n$ 个房间的建筑，房间编号为 $1$ 到 $n$。

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

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

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

之后，我们知道到现在为止共发生了恰好 $k$ 次移动。

我们关注现在这 $n$ 个房间中每个人数的情况。可能有多少种不同的人数组合？

请计算这个组合数对 $(10^9 + 7)$ 取模的结果。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

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 modulo $(10^9 + 7)$.

Constraints

• All values in input are integers.
• $3 \leq n \leq 2 \times 10^5$
• $2 \leq k \leq 10^9$

Input

Input is given from Standard Input in the following format:

$n$ $k$

Output

Print the number of possible combinations of numbers of people in the $n$ rooms now, modulo $(10^9 + 7)$.

Sample Input 1

3 2

Sample Output 1

10

Let $c_1$, $c_2$, and $c_3$ be the number of people in Room $1$, $2$, and $3$ now, respectively. There are $10$ possible combination of $(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)$

For example, $(c_1, c_2, c_3)$ will be $(0, 1, 2)$ if the person in Room $1$ goes to Room $2$ and then one of the persons in Room $2$ goes to Room $3$.

Sample Input 2

200000 1000000000

Sample Output 2

607923868

Print the count modulo $(10^9 + 7)$.

Sample Input 3

15 6

Sample Output 3

22583772

update @ 2024/3/10 17:16:11