← 返回题目列表

AtCoder · abc194_f

F. 十六进制数字天堂

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

在这个问题中,十六进制表示法使用 0, ..., 9, A, ..., F,分别表示值 0 到 15。
除非另有说明,所有数字表示法均为十进制表示法。

之间有多少个整数 1 和 N (含)完全有 K 十六进制表示法中的不同数字没有前导零?
打印此计数模数 (10^9 + 7).

约束

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

输入

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

N K

在这里, N 采用十六进制表示法。

输出

打印计数模数 10^9 + 7.


示例输入 1

10 1

示例输出 1

15

十六进制数 N is 16 十进制。
在十六进制中,介于 1 和 16 写法如下:

  • 1 通过 15:是 1- 十六进制数字,包含一位不同的数字。
  • 16:是 10 十六进制,包含两个不同的数字。

因此,有 15 包含一位不同的十六进制数字的数字。


示例输入 2

FF 2

示例输出 2

225

所有的 如果 Edge 满足 255 数字,以下除外 30 数字包含两个不同的十六进制数字: 1, 2, 3, \dots, \mathrm{E}, \mathrm{F}, 11, 22, 33, \dots, \mathrm{EE}, \mathrm{FF} 十六进制。


示例输入 3

100 2

示例输出 3

226

示例输入 4

1A8FD02 4

示例输出 4

3784674

示例输入 5

DEADBEEFDEADBEEEEEEEEF 16

示例输出 5

153954073

打印计数模数 (10^9 + 7).