CF497E.Subsequences Return

假设 $s_{k}(n)$ 表示数字 $n$ 在 $k$ 进制下的各位数字之和。例如，$s_{2}(5)=s_{2}(101_{2})=1+0+1=2$，$s_{3}(14)=s_{3}(112_{3})=1+1+2=4$。

定义整数序列 $a_{0},...,a_{n-1}$ 为 $a_{j} = s_{k}(j)\operatorname{mod} k$。你的任务是计算序列 $a_{0},...,a_{n-1}$ 有多少个不同的子序列。请将结果对 $10^9+7$ 取模后输出。

序列 $a_{1},...,a_{k}$ 称为序列 $b_{1},...,b_{l}$ 的一个子序列，如果存在一组下标 $1\leq i_{1}<...<i_{k}\leq l$ ，使得 $a_{1}=b_{i_1},...,a_{k}=b_{i_k}$。特别地，空序列（即不包含任何元素的序列）是任意序列的一个子序列。

第一行包含两个用空格分隔的整数 $n$ 和 $k$（$1\leq n\leq 10^{18}$，$2\leq k\leq 30$）。

输出一行，表示不同子序列的数量，对 $10^9+7$ 取模。

在第一个样例中，序列 $a_{i}$ 为 $(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)$。
在第二个样例中，序列 $a_{i}$ 为 $(0,1,2,3,4,5,6)$。该序列的所有子序列正好是从 $0$ 到 $6$ 的所有递增序列。显然有 $2^{7}=128$ 个这样的序列。

由 ChatGPT 5 翻译