配点 : $500$ 点

問題文

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

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

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

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

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

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

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

制約

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

入力

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

$n$ $k$

出力

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

3 2

10

現在、部屋 $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)$ になります。

200000 1000000000

607923868

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

15 6

22583772