ストーリー

けむにくくんは $N$ 面サイコロを一つ持っています。これを使って $M$ 面サイコロを再現するとき、
サイコロを振る回数の期待値は最小でどのくらいでしょうか？

問題文

$1, 2, \ldots, N$ の目がそれぞれ確率 $\frac{1}{N}$ で出る $N$ 面サイコロがあります。

あなたは、このサイコロを用いて次の操作を行います。

1. サイコロを $1$ 回振る。
2. これまでに出た目の列のみに基づいて、次のいずれかを行う。
   1. $1, 2, \ldots, M$ のいずれか $1$ つを出力し、操作を終了する。
   2. 手順 1 に戻る。

各時点での行動は、それまでに出た目の列のみから決定されるものとし、操作を始める前にあらかじめ定めておきます。

このような操作方法のうち、以下の条件をともに満たすものを 公平な操作方法 と呼びます。

• 確率 $1$ で、有限回の試行によって操作が終了する。
• 各 $i=1,2,\ldots,M$ について、有限回のうちに $i$ を出力して終了する確率が $\frac{1}{M}$ である。

公平な操作方法について、操作が終了するまでにサイコロを振る回数を $T$ とします。

公平な操作方法の中での $T$ の期待値 $\mathbb{E}[T]$ の最小値を求めてください。

なお、制約のもとで公平な操作方法は必ず存在し、また $\mathbb{E}[T]$ の最小値は有限であることが証明できます。

• $2 \leq N \leq 10^{6}$
• $2 \leq M \leq 10^{6}$
• 入力される値はすべて整数である。

• $M = 2$ を満たすデータセットに正解した場合は $50$ 点が与えられる。

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

$N$ $M$

公平な操作方法における $\mathbb{E}[T]$ の最小値を、既約分数 $\frac{A}{B}$ で表す。

このとき、$A B^{-1}$ を $10^9+7$ で割った余りを出力せよ。

ここで、$B^{-1}$ は $B B^{-1}\equiv 1\pmod {10^9+7}$ を満たす整数を表す。
なお、制約のもとで $B$ が $10^9+7$ の倍数にならないことが証明できる。