#abc194f. [abc194_f]Digits Paradise in Hexadecimal

[abc194_f]Digits Paradise in Hexadecimal

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 11 and NN (inclusive) have exactly KK distinct digits in the hexadecimal notation without leading zeros?
Print this count modulo (109+7)(10^9 + 7).

Constraints

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

Input

Input is given from Standard Input in the following format:

NN KK

Here, NN is in hexadecimal notation.

Output

Print the count modulo 109+710^9 + 7.


Sample Input 1

10 1

Sample Output 1

15

The hexadecimal number NN is 1616 in decimal.
In hexadecimal, the integers between 11 and 1616 are written as follows:

  • 11 through 1515: are 11-digit numbers in hexadecimal, containing one distinct digit.
  • 1616: is 1010 in hexadecimal, containing two distinct digits.

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


Sample Input 2

FF 2

Sample Output 2

225

All of the 255255 numbers except the following 3030 numbers contain two distinct digits in hexadecimal: 1,2,3,dots,mathrmE,mathrmF,11,22,33,dots,mathrmEE,mathrmFF1, 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 (109+7)(10^9 + 7).