题目描述

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

• $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)$ で割った余りを求めてください。

输入格式

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

$N$ $K$

输出格式

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

2 2

10

20 17

983853488

提示

制約

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

Sample Explanation 1

長さが $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$ を選ぶ）