题目描述

梦醒了，SudoXue 发现自己被传送到了一处神秘的地方。在这里，屹立着一座被称为互质回响塔的古老装置。

塔的底座共有 $n$ 层，每层都镶嵌若干座星门。第 $j$ 号星门有 $G(j)$ 条独立通路通往主塔核心。

星门通路数 $G(j)$ 的定义：

$$G(j)=\bigl|\{\,1\le t\le j\mid \gcd(t,j)=1\,\}\bigr|. $$

噜噜和一只羊准备向塔内注入能量以收集星尘。游戏按轮次进行：

• 第 $i$ 轮（$1\le i\le n$）注入的能量为 $k^i$ 单位；
• 能量会被均匀散射到层号不大于 $\bigl\lfloor n/i\rfloor$ 的所有星门；
• 本轮可收集的星尘等于

星尘$(i)=k^{\,i}\times\displaystyle\sum_{j=1}^{\lfloor n/i\rfloor} G(j)$

最终得分是把所有轮次获得的星尘相加，再对 $M=10^9+7$ 取模。SudoXue 希望知道最终得分是多少。

---

善良的 SudoXue 觉得上面的问题似乎有点难懂？好心的他提供了简要题面：

给定正整数 $n$ 与 $k$，记

$$F(m)=\sum_{j=1}^{m} G(j)\qquad(1\le m).$$

请计算

• 对每个 $i$（$1\le i\le n$）设 $m_i=\bigl\lfloor n/i\rfloor$；
• 设 $P_i=k^{i}\bmod M$，$S_i=F(m_i)$；
• 总得分为

$$\Bigl(\sum_{i=1}^{n} P_i\cdot S_i\Bigr)\bmod M.$$

输出该结果。

输入格式

一行两个正整数 $n$、$k$。

输出格式

一行一个整数，表示最终得分（对 $10^9+7$ 取模）。

3 2

20

样例解释

• 第 $1$ 轮：$\lfloor 3/1\rfloor=3$，$G(1)+G(2)+G(3)=1+1+2=4$，星尘 $=2^1\times4=8$；
• 第 $2$ 轮：$\lfloor 3/2\rfloor=1$，$G(1)=1$，星尘 $=2^2\times1=4$；
• 第 $3$ 轮：$\lfloor 3/3\rfloor=1$，星尘 $=2^3\times1=8$。

$$8+4+8=20\pmod{10^9+7}.$$

数据规模与约定

子任务	分数占比	约束
$1$	$20\%$	$1\le n\le10^5;1\le k\le10^3$
$2$	$30\%$	$1\le n\le10^8;1\le k\le10^6$
$3$	$50\%$	$1\le n\le10^{10};1\le k\le10^9$