← 返回题目列表

AtCoder · dp_s

S. 数字和

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

查找之间的整数个数 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