問題文

各要素が $1$ 以上 $K$ 以下の整数である要素数 $N$ の数列 $K^N$ 通りすべてについてのその数列の要素の最小値の総和を求めよ。

入力

$N$ $K$

出力

答えを $10^9+7$ で割った余りを1行に出力しなさい。

制約

• $1≦N, K$


• $1≦NK≦10^{12}$

小課題

小課題 1

• $N=1$

小課題 Euglena

• 追加の制約はない。