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

inputFormat

Input

Input is given from Standard Input in the following format:

N K

outputFormat

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

样例

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3

117879300