题目描述

设 $s_k(x)$ 表示 $x$ 在 $k$ 进制下各位数的和 $\bmod\ k$ 的值。给出 $k$，现有序列 $[s_k(0),s_k(1),\ldots, s_k(n-1)]$。

求这个序列有多少个本质不同的子序列。

输入格式

一行两个整数 $n,k$，$1\le n\le 10^{18}$，$2\le k\le 30$。

输出格式

一个整数，表示答案对 $10^{9}+7$ 取余的结果。

4 2

11

7 7

128