時間制限 : sec, メモリ制限 : KB
English / Japanese  

ボールと箱 5

ボール入れ方に制限なし箱の中身は1つ以下箱の中身は1つ以上
区別できる区別できる123
区別できない区別できる456
区別できる区別できない789
区別できない区別できない101112

$n$ 個の区別できないボールを $k$ 個の区別できる箱に入れるとき、その入れ方の総数を求めてください。

ただし、ボールの入れ方は以下のルールにしたがいます:

  • どのボールも、必ずいずれかの箱に入れる。
  • 各箱に入れることのできるボールの数は高々1つまで。

答えは非常に大きくなることがあるので、$10^9+7$ で割った余りを求めてください。

入力

$n$ $k$

2つの整数 $n$、$k$ が空白区切りで1行に与えられる。

出力

ボールの入れ方の総数を $10^9+7$ で割った余りを1行に出力する。

制約

  • $1 \le n \le 1000$
  • $1 \le k \le 1000$

入力例 1

3 5

出力例 1

10

入力例 2

5 10

出力例 2

252

入力例 3

100 200

出力例 3

407336795