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

ボールと箱 12

ボール入れ方に制限なし箱の中身は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

10 5

出力例 1

7

入力例 2

30 15

出力例 2

176

入力例 3

100 30

出力例 3

3910071