题目描述

给定一个非常大的十进制正整数 $N$，再给定一个整数 $D$。

请统计 $1$ 到 $N$ 之中，有多少个十进制整数中恰好有 $D$ 个数字非零。

由于答案可能很大，输出答案模 $10^9+7$ 的余数。

输入格式

• 第一行：单个整数表示 $N$
• 第二行：单个整数表示 $M$

输出格式

100
2

81

数据范围

• $30\%$ 的数据，$1\leq N< 10^6$
• $60\%$ 的数据，$1\leq N< 10^{12}$
• $100\%$ 的数据，$1\leq N< 10^{10000}$
• $1\leq D< 100$

来源

改编自 ABC154E Almost Everywhere Zero