假设 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个。