题目描述

Find the number of integers between $1$ and $N$ (inclusive) that contains exactly $K$ non-zero digits when written in base ten.

求在 $1$ 和 $N$ （含）之间的整数中，以十为底数书写时正好包含 $K$ 个非零数字的整数个数。

输入格式

输入内容按以下格式标准输入：

$N$
$K$

输出格式

打印计数。

样例 #1

样例输入 #1

100
1

样例输出 #1

19

样例 #2

样例输入 #2

25
2

样例输出 #2

14

样例 #3

样例输入 #3

314159
2

样例输出 #3

937

样例 #4

样例输入 #4

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3

样例输出 #4

117879300

说明

数据规模与约定

• $1 \leq N \lt 10^{100}$
• $1 \leq K \leq 3$

样例 $1$ 解释

下列 $19$ 个整数满足条件：

• $1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90,100$

样例 $2$ 解释

下列 $14$ 个整数满足条件：

• $11,12,13,14,15,16,17,18,19,21,22,23,24,25$