配点 : $1000$ 点

問題文

以下のようなゲームを考えます。

• $1$ 列に並んだ $N$ 個のマスとたくさんの石を用意する。
• 最初に、マス $i\ (1 \leq i \leq N)$ に $a_i$ 個の石を入れる。
• プレイヤーは「ちょうど $i$ 個の石が入っているようなマス $i$ を $1$ つ選び、そこに入っている石を全て捨て、マス $1$ からマス $i-1$ までの $i-1$ 個のマスに石を $1$ つずつ追加する」という操作を好きなだけ行う。
• 最終的にマスに残った石の個数の合計がスコアとなる。

長さ $N$ の数列 $a$ に対してこのゲームを行ったときのスコアとして考えられる最小値を $f(a)$ とします。

このとき、長さが $N$ で各要素が $0$ 以上 $K$ 以下であるような全ての数列 $a$ についての $f(a)$ の総和はいくつになるでしょうか？ 答えは非常に大きくなる可能性があるため、$1000000007 (= 10^9+7)$ で割った余りを求めてください。

制約

• $1 \leq N \leq 100$
• $1 \leq K \leq N$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$

出力

$f(a)$ の総和を $1000000007 (= 10^9+7)$ で割った余りを出力せよ。

2 2

10

長さが $2$ で各要素が $0$ 以上 $2$ 以下であるような数列 $a$ は $9$ 通り考えられますが、それぞれに対する $f(a)$ の値とそれを達成するための操作の例は以下の通りです。

• $f(\{0,0\})$：$0$（なにも操作できない）
• $f(\{0,1\})$：$1$（なにも操作できない）
• $f(\{0,2\})$：$0$（マス $2$ 、マス $1$ の順に操作する）
• $f(\{1,0\})$：$0$（マス $1$ を選ぶ）
• $f(\{1,1\})$：$1$（マス $1$ を選ぶ）
• $f(\{1,2\})$：$0$（マス $1$ 、マス $2$ 、マス $1$ の順に操作する）
• $f(\{2,0\})$：$2$（なにも操作できない）
• $f(\{2,1\})$：$3$（なにも操作できない）
• $f(\{2,2\})$：$3$（マス $2$ を選ぶ）

20 17

983853488