AT_ttpc2015_j 指さし

[problemUrl]: https://atcoder.jp/contests/ttpc2015/tasks/ttpc2015_j $ N $人がいて、それぞれ自分以外の誰か$ 1 $人を指さしています。このとき、誰からも指さされていない人は一人もいませんでした。 各人が指さされている指を何回辿ったときにはじめて自分自身に戻ってくるか報告したところ、その最大値は$ K $回でした。 このような指さし方がいくつあるか数えてみましょう。 指さし方を数える際、人はそれぞれ区別するものとします。 指さし方の通り数は非常に大きくなりうるので、$ 1,000,000,007(=10^{9}+7) $で割った余りを求めなさい。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ - $ 1 $ 行目に整数$ N(2\ \leq\ N\ \leq\ 1000) $、$ K(1\ \leq\ K\ \leq\ N) $が空白区切りで与えられる。

指さし方の通り数を$ 1,000,000,007 $で割った余りを1行で出力せよ。 出力の末尾に改行を入れること。

### 部分点 この問題には部分点が設定されている。 - $ 2\ \leq\ N\ \leq\ 8 $を満たすデータセットに正解した場合$ 10 $点が得られる。 - 全てのデータセットに正解した場合はさらに$ 140 $点が得られる。合計で$ 150 $点となる。 ### Sample Explanation 1 それぞれの人を$ 1 $、$ 2 $、$ 3 $としたとき、$ 1 $→$ 2 $→$ 3 $→$ 1 $となる指さし方と、$ 1 $→$ 3 $→$ 2 $→$ 1 $となる指さし方の2通りが存在します。 ### Sample Explanation 2 それぞれの人を$ 1 $、$ 2 $、$ 3 $、$ 4 $としたとき、$ 1 $→$ 2 $→$ 1 $、$ 3 $→$ 4 $→$ 3 $となる指さし方と、$ 1 $→$ 3 $→$ 1 $、$ 2 $→$ 4 $→$ 2 $となる指さし方と、$ 1 $→$ 4 $→$ 1 $、$ 2 $→$ 3 $→$ 2 $となる指さし方の3通りが存在します。 ### Sample Explanation 3 条件を満たす指さし方が存在しないこともあります。 ### Sample Explanation 4 答えは非常に大きくなりうるので、$ 1,000,000,007 $で割った余りを出力してください。