问题描述

在这个问题中，十六进制表示法使用 0, ..., 9, A, ..., F 分别表示值为零到十五的数。
除非另有说明，否则所有数字的表示法都是十进制表示法。

在十六进制表示法中，介于 $1$ 和 $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)$ 的模。

---

示例输入 1

10 1

示例输出 1

15

十六进制数 $N$ 在十进制中对应数值 $16$。
在十六进制中，介于 $1$ 和 $16$ 之间的整数如下所示：

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

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

---

示例输入 2

FF 2

示例输出 2

225

除以下 $30$ 个数外，其余 $255$ 个数在十六进制中都包含两个不同的数字：十六进制数 $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)$ 的模。