J - 指さし Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

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点となる。

入力例1

3 3

出力例1

2

それぞれの人を1、2、3としたとき、1→2→3→1となる指さし方と、1→3→2→1となる指さし方の2通りが存在します。

入力例2

4 2

出力例2

3

それぞれの人を1、2、3、4としたとき、1→2→1、3→4→3となる指さし方と、1→3→1、2→4→2となる指さし方と、1→4→1、2→3→2となる指さし方の3通りが存在します。

入力例3

3 2

出力例3

0

条件を満たす指さし方が存在しないこともあります。

入力例4

1000 1000

出力例4

756641425

答えは非常に大きくなりうるので、1,000,000,007で割った余りを出力してください。