AT_abc156_e [ABC156E] Roaming

[problemUrl]: https://atcoder.jp/contests/abc156/tasks/abc156_e $ n $ 個の部屋がある建物があります。 部屋には $ 1 $ から $ n $ までの番号が付いています。 建物の各部屋から、他の任意の部屋に移ることが可能です。 ここで、建物のある部屋 $ i $ にいる人が、別の部屋 $ j~\ (i\ \neq\ j) $ に移ることを **人の移動** と呼ぶことにします。 最初、建物の各部屋には人が $ 1 $ 人いました。 このあと現在までに、人の移動がちょうど $ k $ 回起きたことが分かっています。 現在、建物の各部屋にいる人の数の組合せとして、ありえるものは何通りでしょうか。 $ (10^9\ +\ 7) $ で割った余りを求めてください。

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

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

### 制約 - 入力は全て整数である。 - $ 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) $ で割った余りを出力してください。