F - 十六进制的数字天堂

分数：600 分

问题描述

在本问题中，十六进制表示法使用字符0到9，A到F，分别表示0到15这16个不同的值。 除非另有说明，所有的数字都是以十进制表示法给出的。

在十六进制表示法下，长度在$1$到$N$（包含$N$）之间，且恰好有$K$个不同的数字的整数有多少个？ 把这个计数值对 $(10^9 + 7)$ 取模后输出。

约束

• $1 \le N \lt {16}^{2 \times 10^5}$
• $N$ 以十六进制表示法给出，没有前导 $0$。
• $1 \le K \le 16$
• 输入的所有值都是整数。

输入

从标准输入读入以下格式的内容：

$N$ $K$

这里，$N$ 以十六进制表示法给出。

输出

把计数值对 $10^9 + 7$ 取模后输出。

10 1

15

十六进制数 $N$ 在十进制下是 $16$。
在十六进制下，数字 $1$ 到 $16$ 的表示如下：

• $1$ 到 $15$：这些是十六进制下的 $1$ 位数，包含一个不同的数字。
• $16$：在十六进制下是 $10$，包含两个不同的数字。

因此，在十六进制中，有 $15$ 个只包含一个不同数字的数字。

FF 2

225

在十六进制表示法下，除了以下 $30$ 个数字外，其余的 $255$ 个数字都有两个不同的数字：在十六进制下，$1, 2, 3, \dots, \mathrm{E}, \mathrm{F}, 11, 22, 33, \dots, \mathrm{EE}, \mathrm{FF}$。

100 2

226

1A8FD02 4

3784674

DEADBEEFDEADBEEEEEEEEF 16

153954073

输出时对 $(10^9 + 7)$ 取模。