配点 : $100$ 点

問題文

$1$ 以上 $K$ 以下の整数のうち、十進表記における各桁の数字の総和が $D$ の倍数であるようなものは何個でしょうか？ $10^9 + 7$ で割った余りを求めてください。

制約

• 入力はすべて整数である。
• $1 \leq K < 10^{10000}$
• $1 \leq D \leq 100$

入力

入力は以下の形式で標準入力から与えられる。

$K$

$D$

出力

条件を満たす整数は何個か？ $10^9 + 7$ で割った余りを出力せよ。

30
4

6

$4, 8, 13, 17, 22, 26$ の $6$ 個です。

1000000009
1

2

答えを $10^9 + 7$ で割った余りを出力することを忘れずに。

98765432109876543210
58

635270834