ボールと箱 3

ボール	箱	入れ方に制限なし	箱の中身は1つ以下	箱の中身は1つ以上
区別できる	区別できる	1	2	3
区別できない	区別できる	4	5	6
区別できる	区別できない	7	8	9
区別できない	区別できない	10	11	12

$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

4 3

出力例 1

36

入力例 2

10 3

出力例 2

55980

入力例 3

100 100

出力例 3

437918130

---