問題文

(難易度目安:$400$点)

長さ$N$の自然数のみから構成される数列$A$を考えます。

ただし、$A$の要素は以下の制約を満たします。

◉$1\le i \le N なる自然数iに対して 1 \le A[i] \le K$

また、数列$A$の「コスト」を以下で定義します。

◎$1 \le i < j \le N なる自然数のペア(i,j)に対しての min(A[i],A[j])の総和$

条件を満たす数列は全てで$K ^ N$個考えられますが、この全てに対し数列のコストを計算し、その期待値を$mod\ 10^9 +7$で求めてください。

制約

・$1\le N ,K \le 200000$

・入力はすべて整数

入力

入力は以下の形式で与えられます。

N K 

出力

求める期待値を$E$とすると、$E$は互いに素で分母が$10 ^ 9 + 7$で割り切れないような既約分数の形で表せます。

$E = \frac{p}{q}$

とする時、$pq^{-1} (mod\ 10 ^ 9 + 7)$を出力してください。

最後に改行してください。

サンプル

3 2

750000009

考えうる数列$A$は$8$通り存在し、その全てについてコストを計算すると以下のようになります。

$A : [1, 1, 1] → 3$

$A : [1, 1, 2] → 3$

$A : [1, 2, 1] → 3$

$A : [1, 2, 2] → 4$

$A : [2, 1, 1] → 3$

$A : [2, 1, 2] → 4$

$A : [2, 2, 1] → 4$

$A : [2, 2, 2] → 6$

したがって、コストの期待値は$\frac{30}{8} = \frac{15}{4} = 3.75$であり、その$mod\ 10^9 + 7$での値$750000009$を出力します。

6 10

750000063

期待値は$\frac{231}{4}$です。

8 8

250000091

期待値は$\frac{357}{4}$です。

200000 200000

907299983

期待値は$\frac{5333346666533333}{4}$です。