子序列归来

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

记 $s_k(n)$ 为非负整数 $n$ 在 $k$ 进制下的各位数字之和。例如，$s_2(5)=s_2(101_2)=2$，$s_3(14)=s_3(112_3)=4$。

定义长度为 $n$ 的序列

求序列 $a_0,a_1,\ldots,a_{n-1}$ 有多少个不同的子序列。空序列也算一个子序列。答案对 $10^9+7$ 取模。

输入格式

一行两个整数 $n,k$。

输出格式

输出不同子序列的数量对 $10^9+7$ 取模后的结果。

样例输入 1

4 2

样例输出 1

11

样例输入 2

7 7

样例输出 2

128

数据范围

$1\le n\le10^{18}$，$2\le k\le30$。

说明

第一个样例对应序列 $(0,1,1,0)$，共有 $11$ 个不同子序列。第二个样例中各项互不相同，因此所有 $2^7$ 种选取方式都得到不同序列。