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

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