该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

受限非零数位

题目描述

给定一个正整数 $N$，以及两个整数 $K,D$。

请统计满足下列全部条件的正整数 $x$ 的个数：

1. $1\le x\le N$；
2. $x$ 的十进制表示中恰好有 $K$ 个非零数位；
3. 每个非零数位都不超过 $D$。

十进制表示不包含前导零。例如，$1020$ 有两个非零数位，分别为 $1$ 和 $2$。

输入格式

第一行输入一个十进制正整数 $N$，保证 $1\le N<10^{100}$，且 $N$ 不含前导零。

第二行输入两个整数 $K,D$，满足 $1\le K\le 3$，$1\le D\le 9$。

输出格式

输出满足条件的正整数个数。

输入输出样例 #1

输入 #1

25
1 2

输出 #1

4

输入输出样例 #2

输入 #2

120
2 1

输出 #2

3

说明/提示

样例 1 中，满足条件的数为 $1,2,10,20$。

样例 2 中，满足条件的数为 $11,101,110$。