十六进制中的数字种类

题目描述

在本问题中,十六进制表示中把 0 ~ 9, A ~ F 作为数字处理,A ~ F 分别表示十到十五。

另外,除非特别说明,问题文中处理的数全部用十进制表示。

在 $1$ 以上 $N$ 以下的整数中,用不带前导 0 的十六进制表示写出时,恰好出现 $K$ 种数字的有多少个呢?

请输出除以 $10^9 + 7$ 的余数。

输入格式

输入按以下格式从标准输入给出:

$N$ $K$

$N$ 用十六进制表示给出。

输出格式

输出答案除以 $10^9 + 7$ 的余数。

样例

10 1

15

$N$ 用十六进制表示给出,换算成十进制是 $16$。

将 $1$ 以上 $16$ 以下的整数用不带前导 0 的十六进制表示写出,如下所示:

• $1$ 到 $15$:换算成十六进制是 $1$ 位,因此出现的数字是 $1$ 种
• $16$:换算成十六进制是 $10$,因此出现的数字是 $2$ 种

因此,换算成十六进制后出现的数字为 $1$ 种的有 $15$ 个。

FF 2

225

出现的数字为 $2$ 种的,是 $1$ 以上 $255$ 以下的 $255$ 个整数中,除去用十六进制表示为 $1, 2, 3, \dots, \mathrm{E}, \mathrm{F}, 11, 22, 33, \dots, \mathrm{EE}, \mathrm{FF}$ 的 $15 + 15 = 30$ 个之后的那些数。

100 2

226

1A8FD02 4

3784674

DEADBEEFDEADBEEEEEEEEF 16

153954073

请输出答案除以 $10^9 + 7$ 的余数。

数据范围

• $1 \le N \lt {16}^{2 \times 10^5}$
• $N$ 用不带前导 0 的十六进制表示给出
• $1 \le K \le 16$
• 输入中包含的值均为整数