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

Input is given from Standard Input in the following format:

```
$N$ $K$
```

Here, $N$ is in hexadecimal notation.

Print the count modulo $10^9 + 7$.

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

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.

225

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