问题描述

找到在$1$到$K$之间的整数中满足以下条件的数量，对$10^9 + 7$取模：

• 十进制表示中各位数字之和是$D$的倍数。

约束条件

• 输入中的所有值均为整数。
• $1 \leq K < 10^{10000}$
• $1 \leq D \leq 100$

输入

输入以以下格式从标准输入中给出：

$K$

$D$

输出

输出满足条件的整数的数量，对$10^9 + 7$取模。

示例输入1

30
4

示例输出1

6

满足条件的六个整数是：$4, 8, 13, 17, 22$和$26$。

示例输入2

1000000009
1

示例输出2

2

注意要对结果取模$10^9 + 7$。

示例输入3

98765432109876543210
58

示例输出3

635270834