#AT19. Digit Sum

Digit Sum

[S] Digit Sum(dp_s)

来源: AtCoder Educational DP Contest - Problem S 原题时限:2 秒 / 内存:1024 MB

题目描述

求 11 到 KK(含两端)之间,满足下列条件的整数个数,对 109+710^9 + 7 取模:

  • 该整数在十进制下的各位数字之和是 DD 的倍数。

输入格式

输入由标准输入按以下格式给出:

K
D

其中 KK 最多可能有 1000010000 位十进制数字。

输出格式

输出满足条件的整数个数对 109+710^9 + 7 取模的结果。

数据范围

  • 1≤K<10100001 \le K < 10^{10000}
  • 1≤D≤1001 \le D \le 100

样例 1

输入:

30
4

输出:

6

样例 2

输入:

1000000009
1

输出:

2

样例 3

输入:

98765432109876543210
58

输出:

635270834