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

ボールと箱 2

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

2 3

出力例 1

6

入力例 2

3 2

出力例 2

0

入力例 3

100 100

出力例 3

437918130