← 返回题目列表

AtCoder · abc239_h

Ex. 骰子产品 2

中文机器翻译题面 查看原题

分数: 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