Digits Paradise in Hexadecimal

题目描述

在这个问题中，十六进制表示法使用 $0$, ..., $9$, $A$, ..., $F$，分别表示值从零到十五。
除非另有说明，所有数字的表示均为十进制表示法。 在十六进制表示（不含前导零）的情况下，介于 $1$ 与 $N$（包含端点）之间有多少整数恰好包含 $K$ 个不同的数字？
将该数量对 $(10^9 + 7)$ 取模后输出。

输入格式

输入由标准输入提供，格式如下： $N$ $K$

其中，$N$ 为十六进制表示。

输出格式

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

10 1

15

FF 2

225

100 2

226

1A8FD02 4

3784674

DEADBEEFDEADBEEEEEEEEF 16

153954073

提示

$1 \le N \lt {16}^{2 \times 10^5}$ $N$ 以十六进制表示，不含前导 $0$。 $1 \le K \le 16$ 输入中的所有数值均为整数。十六进制数 $N$ 的十进制值为 $16$。
在十六进制中，介于 $1$ 与 $16$ 之间的整数写法如下：

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

因此，包含一个不同数字的数有 $15$ 个。
在十六进制中，除了以下 $30$ 个数以外，所有 $255$ 个数都包含两个不同的数字：$1, 2, 3, \dots, \mathrm{E}, \mathrm{F}, 11, 22, 33, \dots, \mathrm{EE}, \mathrm{FF}$。
将该数量对 $(10^9 + 7)$ 取模后输出。

标签: AtCoder|abc194F

来源

AtCoder|abc194F