题目描述

给定两个正整数 $N,K$，求出 $1$ 到 $N$ 中有多少个正整数，满足它的非零数位个数和恰好等于 $K$。

输入格式

一行，空格隔开的两个数表示 $N,K$。

输出格式

满足条件数的个数。

样例 #1

样例输入 #1

100
1

样例输出 #1

19

样例1解释

满足条件的数共$19$ 个如下：

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

样例 #2

样例输入 #2

25
2

样例输出 #2

14

样例 #3

样例输入 #3

314159
2

样例输出 #3

937

样例 #4

样例输入 #4

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3

样例输出 #4

117879300

数据规模

100%的数据：

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

10%的数据：

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

50%的数据：

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