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

见题面

见题面