配点 : $600$ 点

問題文

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

$1$ 以上 $N$ 以下の整数のうち、先頭に $0$ のない十六進表記で書くとちょうど $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$ で割ったあまりを出力せよ。

10 1

15

$N$ は十六進表記で与えられているため、十進数に直すと $16$ です。 $1$ 以上 $16$ 以下の整数を、先頭に $0$ のない十六進表記で書くと下記のようになります。

• $1$ から $15$ まで : 十六進表記に直すと $1$ 桁なので、出現する数字は $1$ 種類である
• $16$ : 十六進表記に直すと $10$ なので、出現する数字は $2$ 種類である

よって、十六進表記に直した時に出現する数字が $1$ 種類なのは $15$ 個です。

FF 2

225

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

100 2

226

1A8FD02 4

3784674

DEADBEEFDEADBEEEEEEEEF 16

153954073

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