分数: 600 点
问题陈述
Snuke 有一个骰子(骰子的单数),显示来自 1 通过 N 具有相同的概率,并且是一个整数 1.
当他的整数小于或等于时,他重复以下操作 M.
- 他掷骰子。 如果骰子显示一个整数 x,他将整数乘以 x.
求他掷骰子直到停止的次数的期望值,取模 10^9+7.
期望值模的定义 10^9+7
我们可以证明期望的期望值始终是有理数。 而且,在问题的约束下,当值表示为不可约分数时 \frac{P}{Q},我们还可以证明 Q \not\equiv 0 \pmod{10^9+7}。 因此,一个整数 R 这样 R \times Q \equiv P \pmod{10^9+7} 和 0 \leq R \lt 10^9+7 是唯一确定的。 回答这样的 R.约束
- 2 \leq N \leq 10^9
- 1 \leq M \leq 10^9
输入
输入由标准输入按以下格式给出:
N M
输出
打印答案。
示例输入 1
2 1
示例输出 1
2
答案是滚动次数的期望值,直到显示 2 第一次。 因此, 应打印 2 。
示例输入 2
2 39
示例输出 2
12
答案是滚动次数的期望值,直到显示 2 六次。 因此, 12 。
示例输入 3
3 2
示例输出 3
250000004
答案是 \frac{9}{4}。 我们有 4 \times 250000004 \equiv 9 \pmod{10^9+7},所以 250000004 。
请注意,答案应以模数形式打印 \bf{10^9 + 7 = 1000000007}.
示例输入 4
2392 39239
示例输出 4
984914531
示例输入 5
1000000000 1000000000
示例输出 5
776759630