← 返回题目列表

Codeforces · 1097/D

D. 诚和黑板

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

Makoto 有一块大黑板,上面写着一个正整数$$$n$$$。他将执行以下操作恰好 $$$k$$$ 次:

假设黑板上当前写的数字是$$$v$$$。他将随机选择 $$$v$$$ 的除数之一(可能是 $$$1$$$ 和 $$$v$$$)并用该除数替换 $$$v$$$。由于 Makoto 使用他著名的随机数生成器 (RNG),并且他总是使用 $$$58$$$ 作为生成器种子,因此保证以相同的概率选择每个除数。

他现在想知道经过 $$$k$$$ 步后黑板上写下的数字的预期值是多少。

可以证明,该值可以表示为 $$$\frac{P}{Q}$$$,其中 $$$P$$$ 和 $$$Q$$$ 是互质整数,$$$Q \not\equiv 0 \pmod{10^9+7}$$$。打印 $$$P \cdot Q^{-1}$$$ 模 $$$10^9+7$$$ 的值。

输入

输入的唯一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 10^{15}$$$, $$$1 \leq k \leq 10^4$$$)。

输出

打印一个整数 — $$$k$$$ 步骤后黑板上数字的预期值 $$$P \cdot Q^{-1} \pmod{10^9+7}$$$ 对于上面定义的 $$$P$$$、$$$Q$$$。

示例

输入 #1

6 1

输出 #1

3

输入 #2

6 2

输出 #2

875000008

输入 #3

60 5

输出 #3

237178099

注意

在第一个示例中,一步之后,黑板上写的数字是 $$$1$$$、$$$2$$$、$$$3$$$ 或 $$$6$$$ — 每个出现的概率相等。因此,答案是$$$\frac{1+2+3+6}{4}=3$$$。

在第二个示例中,答案等于 $$$1 \cdot \frac{9}{16}+2 \cdot \frac{3}{16}+3 \cdot \frac{3}{16}+6 \cdot \frac{1}{16}=\frac{15}{8}$$$。