101564: [AtCoder]ABC156 E - Roaming

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $500$ points

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

Input

题意翻译

有 $n$ 不同个房间,每个房间有 $1$ 个人。人可以在各个房间中移动(不能原地移动)。所有人一共移动了 $k$ 次,问最后各个房间人数排列有多少种情况。

加入题单

上一题 下一题 算法标签: