题目描述

找到十进制表示时，介于 $1$ 和 $N$（包括两端）之间恰好包含 $K$ 个非零数字的整数的数量。

约束条件

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

输入

从标准输入读入数据，格式如下：

$N$ $K$

输出

打印答案。

示例输入 1

100
1

示例输出 1

19

满足条件的数有以下 $19$ 个：

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

示例输入 2

25
2

示例输出 2

14

满足条件的数有以下 $14$ 个：

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

示例输入 3

314159
2

示例输出 3

937

示例输入 4

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3

示例输出 4

117879300