AT_dp_s Digit Sum

题目描述

在 $1$ 到 $K$ 之间的整数中，有多少个整数满足其十进制表示的各位数字之和是 $D$ 的倍数？请输出答案对 $10^9 + 7$ 取模后的结果。

输入格式

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

$K$ $D$

输出格式

请输出满足条件的整数个数，对 $10^9 + 7$ 取模后的结果。

输入输出样例 #1

输入 #1

30
4

输出 #1

6

输入输出样例 #2

输入 #2

1000000009
1

输出 #2

2

输入输出样例 #3

输入 #3

98765432109876543210
58

输出 #3

635270834

说明/提示

限制条件

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

样例解释 1

有 $6$ 个数分别为 $4,\ 8,\ 13,\ 17,\ 22,\ 26$。

样例解释 2

请不要忘记将答案对 $10^9 + 7$ 取模后输出。

由 ChatGPT 4.1 翻译