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}$$$。