10849: ABC154 - E - Almost Everywhere Zero
[Creator : ]
Description
Find the number of integers between $1$ and $N$ (inclusive) that contains exactly $K$ non-zero digits when written in base ten.
Input
Input is given from Standard Input in the following format:
```
$N$
$K$
```
```
$N$
$K$
```
Output
Print the count.
Constraints
- $1 \leq N < 10^{100}$
- $1 \leq K \leq 3$
- $1 \leq K \leq 3$
Sample 1 Input
100
1
Sample 1 Output
19
The following $19$ integers satisfy the condition:
- $1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90,100$
Sample 2 Input
25
2
Sample 2 Output
14
The following $14$ integers satisfy the condition:
- $11,12,13,14,15,16,17,18,19,21,22,23,24,25$
Sample 3 Input
314159
2
Sample 3 Output
937
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3
117879300