该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

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

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

• 第 $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$，记

请计算

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

输出该结果。

输入格式

一行两个正整数 $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$。

数据规模与约定