AT_abc194_f [ABC194F] Digits Paradise in Hexadecimal

题目描述

在本题中，十六进制表示中将 0 到 9、A 到 F 作为数字，其中 A 到 F 分别表示十到十五。 除非特别说明，题目中出现的所有数字均为十进制表示。

请计算 $1$ 到 $N$ 之间（包含 $N$）的所有整数中，有多少个数在其十六进制表示（且首位不为 $0$）时，恰好出现了 $K$ 种不同的数字？ 请输出答案对 $10^9+7$ 取模的结果。

输入格式

输入通过标准输入给出，格式如下：

$N$ $K$

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

输出格式

请输出答案对 $10^9+7$ 取模后的结果。

样例 1

输入

10 1

输出

15

样例 2

输入

FF 2

输出

225

样例 3

输入

100 2

输出

226

样例 4

输入

1A8FD02 4

输出

3784674

样例 5

输入

DEADBEEFDEADBEEEEEEEEF 16

输出

153954073

说明/提示

约束条件

• $1 \leq N < 16^{2 \times 10^5}$
• $N$ 的十六进制表示首位不为 0
• $1 \leq K \leq 16$
• 输入中的所有值均为整数

样例解释 1

由于 $N$ 以十六进制表示，转换为十进制后为 $16$。$1$ 到 $16$ 的整数，其十六进制表示如下：

• $1$ 到 $15$：十六进制表示为一位数，因此只出现 $1$ 种数字
• $16$：十六进制表示为 $10$，出现了 $2$ 种数字

因此，十六进制表示中出现 $1$ 种数字的有 $15$ 个。

样例解释 2

出现 $2$ 种数字的情况是：在 $1$ 到 $255$ 的 $255$ 个整数中，十六进制表示为 $1, 2, 3, \dots, E, F, 11, 22, 33, \dots, EE, FF$ 的 $15+15=30$ 个数被排除。

样例解释 5

请输出答案对 $10^9+7$ 取模的结果。

由 ChatGPT 4.1 翻译