101945: [AtCoder]ABC194 F - Digits Paradise in Hexadecimal

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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)$.

Input

题意翻译

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

加入题单

上一题 下一题 算法标签: