骰子乘积 2

题目描述

Snuke 有一个骰子(等概率显示从 $1$ 到 $N$ 的整数),以及一个整数 $1$。

当他的整数小于等于 $M$ 时,他重复以下操作。

他掷骰子。如果骰子显示整数 $x$,他就将自己的整数乘以 $x$。

求他停止之前掷骰子次数的期望值,对 $10^9+7$ 取模(参见提示)。

输入格式

输入按以下格式从标准输入给出:

N M

输出格式

输出答案。

样例

2 1

2

答案是直到第一次出现 $2$ 为止的掷骰子次数的期望值。因此应输出 $2$。

2 39

12

答案是直到出现 $2$ 六次为止的掷骰子次数的期望值。因此应输出 $12$。

3 2

250000004

答案是 $\frac{9}{4}$。由于 $4 \times 250000004 \equiv 9 \pmod{10^9+7}$,应输出 $250000004$。

注意,答案应以模 $\bf{10^9 + 7 = 1000000007}$ 输出。

2392 39239

984914531

1000000000 1000000000

776759630

数据范围

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

提示

可以证明,所求期望值总是有理数。此外,在本问题的约束条件下,当该值用互质的整数 $P$ 和 $Q$ 表示为不可约分数 $\frac{P}{Q}$ 时,可以证明 $Q \not\equiv 0 \pmod{10^9+7}$。因此,满足 $R \times Q \equiv P \pmod{10^9+7}$ 且 $0 \leq R \lt 10^9+7$ 的整数 $R$ 是唯一确定的。输出这样的 $R$。