题目描述

この問題において、十六進表記では 0 ~ 9, A ~ F を数字として扱い、A ~ F はそれぞれ十から十五を表すものとします。
また、特別の記述がない限り問題文中で扱われる数は全て十進表記されているものとします。

$1$ 以上 $N$ 以下の整数のうち、先頭に $0$ のない十六進表記で書くとちょうど $K$ 種類の数字が現れるようなものはいくつあるでしょうか ?
$10^9\ +\ 7$ で割ったあまりを出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $K$

$N$ は十六進表記で与えられる。

输出格式

答えを $10^9\ +\ 7$ で割ったあまりを出力せよ。

题目大意

给你一个长度为 $2 \times 10^5$ 的 $16$ 进制字符串 $N$，让你求出在 $[1,N]$ 中所有的 $16$ 进制数，有多少满足刚好有 $K$ 个不同的数位（不包含前导 $0$）。

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$
• 入力に含まれる値は全て整数

Sample Explanation 1

$N$ は十六進表記で与えられているため、十進数に直すと $16$ です。 $1$ 以上 $16$ 以下の整数を、先頭に $0$ のない十六進表記で書くと下記のようになります。 - $1$ から $15$ まで : 十六進表記に直すと $1$ 桁なので、出現する数字は $1$ 種類である - $16$ : 十六進表記に直すと $10$ なので、出現する数字は $2$ 種類である よって、十六進表記に直した時に出現する数字が $1$ 種類なのは $15$ 個です。

Sample Explanation 2

出現する数字が $2$ 種類なのは、$1$ 以上 $255$ 以下の $255$ 個の整数のうち、十六進表記で $ 1,\ 2,\ 3,\ \dots,\ \mathrm{E},\ \mathrm{F},\ 11,\ 22,\ 33,\ \dots,\ \mathrm{EE},\ \mathrm{FF} $ と表される $15\ +\ 15\ =\ 30$ 個を除いたものです。

Sample Explanation 5

答えを $10^9\ +\ 7$ で割った余りを出力してください。