题目描述

$n$ 個の部屋がある建物があります。 部屋には $1$ から $n$ までの番号が付いています。

建物の各部屋から、他の任意の部屋に移ることが可能です。

ここで、建物のある部屋 $i$ にいる人が、別の部屋 $j~\ (i\ \neq\ j)$ に移ることを 人の移動 と呼ぶことにします。

最初、建物の各部屋には人が $1$ 人いました。

このあと現在までに、人の移動がちょうど $k$ 回起きたことが分かっています。

現在、建物の各部屋にいる人の数の組合せとして、ありえるものは何通りでしょうか。

$(10^9\ +\ 7)$ で割った余りを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$n$ $k$

输出格式

現在、建物の各部屋にいる人の数の組合せとして、ありえるものの個数を $(10^9\ +\ 7)$ で割った余りを出力せよ。

题目大意

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

3 2

10

200000 1000000000

607923868

15 6

22583772

提示

制約

• 入力は全て整数である。
• $3\ \leq\ n\ \leq\ 2\ \times\ 10^5$
• $2\ \leq\ k\ \leq\ 10^9$

Sample Explanation 1

現在、部屋 $1$ にいる人の数を $c_1$、部屋 $2$ にいる人の数を $c_2$、部屋 $3$ にいる人の数を $c_3$ と すると、$(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)$ の $10$ 通りです。 例えば、まず部屋 $1$ にいる人が部屋 $2$ に移動し、 次に部屋 $2$ にいる誰かが部屋 $3$ に移動した場合を考えると、 $(c_1,\ c_2,\ c_3)$ は $(0,\ 1,\ 2)$ になります。

Sample Explanation 2

個数を $(10^9\ +\ 7)$ で割った余りを出力してください。