p02781 AtCoder Beginner Contest 154 - Almost Everywhere Zero
Find the number of integers between 1 and N (inclusive) that contains exactly K non-zero digits when written in base ten.

Constraints

* 1 \leq N < 10^{100}
* 1 \leq K \leq 3

Input

Input is given from Standard Input in the following format:


N
K


Output

Print the count.

Examples

Input

100
1


Output

19


Input

25
2


Output

14


Input

314159
2


Output

937


Input

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3


Output

117879300
```python
import functools
import sys


@functools.lru_cache(None)
def doit(n, k):
    if len(n) == 0 or k < 0:
        return k == 0
    d = int(n[0])
    return sum(doit(n[1:] if i == d else '9' * (len(n) - 1), k - 1 if i > 0 else k) for i in range(d + 1))


sys.setrecursionlimit(404)
print(doit(input(), int(input())))

```