← 返回题目列表

Codeforces · 497/E

E. 子序列返回

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

假设 sk(n) 等于基于 k 的表示法中数字 n 的数字之和。例如,s2(5) = s2(1012) = 1 + 0 + 1 = 2,s3(14) = s3(1123) = 1 + 1 + 2 = 4。

整数序列 a0, ..., an - 1 定义为 $$a_{j}=s_{k}(j)\bmod k$$。您的任务是计算序列 a0, ..., an - 1 的不同子序列的数量。计算结果以 109 + 7 为模。

如果存在索引序列 1 ≤ i1 < ... < ik ≤ l,且 a1 = bi1, ..., ak = bik,则序列 a1, ..., ak 被称为序列 b1, ..., bl 的子序列。特别地,空序列(即由零个元素组成的序列)是任何序列的子序列。

输入

第一行包含两个空格分隔的数字 n 和 k (1 ≤ n ≤ 1018, 2 ≤ k ≤ 30)。

输出

在一行中打印出模 109 + 7 的问题答案。

示例

输入 #1

4 2

输出 #1

11

输入 #2

7 7

输出 #2

128

注意

在第一个示例中,序列 ai 如下所示:(0, 1, 1, 0)。所有可能的子序列是:

(), (0), (0, 0), (0, 1), (0, 1, 0), (0, 1, 1), (0, 1, 1, 0), (1), (1, 0), (1, 1), (1, 1, 0).

在第二个示例中,序列 ai 如下所示:(0, 1, 2, 3, 4, 5, 6)。这个序列的子序列恰好都是由0到6的数字组成的递增序列。很容易看出,这样的序列有27 = 128个。