配点 : $600$ 点

問題文

すぬけ君は $1$ 以上 $N$ 以下の整数が等確率で出るサイコロと整数 $1$ を持っています。 すぬけ君は持っている数が $M$ 以下である間、次の操作を繰り返します。

• サイコロを振り、出た目を $x$ とする。持っている数に $x$ を掛ける。

操作を終了するまでにすぬけ君がサイコロを振った回数の期待値を $\text{mod } 10^9+7$ で求めてください。

制約

• $2 \leq N \leq 10^9$
• $1 \leq M \leq 10^9$

入力

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

$N$ $M$

出力

答えを出力せよ。

2 1

2

答えはサイコロで $2$ が出るまでにサイコロを振る回数の期待値になります。よって $2$ を出力します。

2 39

12

答えはサイコロで $2$ が $6$ 回出るまでにサイコロを振る回数の期待値になります。よって $12$ を出力します。

3 2

250000004

答えは $\frac{9}{4}$ です。$4 \times 250000004 \equiv 9 \pmod{10^9+7}$ なので $250000004$ を出力します。 $\bf{10^9 + 7 = 1000000007}$ で $\mathrm{mod}$ を取る必要があるのに注意してください。

2392 39239

984914531

1000000000 1000000000

776759630