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

问题描述

半仙最近在研究一个奇怪的函数，它定义如下：

$ f(n) = \begin{cases} f(\frac{n}{k}), & \text{如果} k \mid n \\ f(n-1)+1, & \text{其他情况} \end{cases} $

其中，$n$ 和 $k$ 都是正整数，$k \mid n$ 表示 $k$ 整除 $n$，即 $n$ 对 $k$ 取模的结果是 $0$。

现在记 $S(n) = \sum_{i=1}^{n} f(i)$，即 $S(n)$ 是 $f$ 函数的前 $n$ 项之和。

你的任务是：输入 $n$ 和 $k$，求 $S(n)$，最后结果对 $10^9 + 7$ 取模。

输入格式

共两行，第一行一个整数 $n$，第二行一个整数 $k$。

输出格式

一个整数表示 $S(n)$ 的值，对 $10^9 + 7$ 取模。

样例

10
2

17

202011146666666666
6

93574825

数据范围

• 对于 30% 的数据：$0 < n \leq 10^8$；
• 对于 50% 的数据：$0 < n \leq 10^{12}$；
• 对于 100% 的数据：$0 < n \leq 10^{18}$，$2 \leq k \leq 10$。