問題文

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

制約

• 入力はすべて整数である。
• $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$ の $6$ 個です。

入力例 2

1000000009
1

出力例 2

2

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

入力例 3

98765432109876543210
58

出力例 3

635270834