F - Digits Paradise in Hexadecimal Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 で割ったあまりを出力せよ。

入力例 1

10 1

出力例 1

15

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

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

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

入力例 2

FF 2

出力例 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 個を除いたものです。

入力例 3

100 2

出力例 3

226

入力例 4

1A8FD02 4

出力例 4

3784674

入力例 5

DEADBEEFDEADBEEEEEEEEF 16

出力例 5

153954073

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

Score : 600 points

Problem Statement

In this problem, hexadecimal notations use 0, ..., 9, A, ..., F, representing the values zero through fifteen, respectively.
Unless otherwise specified, all notations of numbers are decimal notations.

How many integers between 1 and N (inclusive) have exactly K distinct digits in the hexadecimal notation without leading zeros?
Print this count modulo (10^9 + 7).

Constraints

  • 1 \le N \lt {16}^{2 \times 10^5}
  • N is given in hexadecimal notation without leading 0s.
  • 1 \le K \le 16
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K

Here, N is in hexadecimal notation.

Output

Print the count modulo 10^9 + 7.

Sample Input 1

10 1

Sample Output 1

15

The hexadecimal number N is 16 in decimal.
In hexadecimal, the integers between 1 and 16 are written as follows:

  • 1 through 15: are 1-digit numbers in hexadecimal, containing one distinct digit.
  • 16: is 10 in hexadecimal, containing two distinct digits.

Thus, there are 15 numbers that contain one distinct digit in hexadecimal.

Sample Input 2

FF 2

Sample Output 2

225

All of the 255 numbers except the following 30 numbers contain two distinct digits in hexadecimal: 1, 2, 3, \dots, \mathrm{E}, \mathrm{F}, 11, 22, 33, \dots, \mathrm{EE}, \mathrm{FF} in hexadecimal.

Sample Input 3

100 2

Sample Output 3

226

Sample Input 4

1A8FD02 4

Sample Output 4

3784674

Sample Input 5

DEADBEEFDEADBEEEEEEEEF 16

Sample Output 5

153954073

Print the count modulo (10^9 + 7).