题目背景

辛美尔在跪地为芙莉莲带上镜莲花戒指的同时，也向身旁象征时间的钟楼低下了头。

辛美尔的寿命抵不过时间，辛美尔的铜像也经不住时间的风霜。幸好，长寿的精灵会永远记住他的。

题目描述

在芙莉莲近乎永恒的寿命时间里，芙莉莲好奇有多少个年份数字的各位数字和刚好为 $d$ 的倍数。

具体而言，芙莉莲想知道在范围 $1$ 到 $k$ 的所有数字中，有多少个数字，其十进制各数位之和为 $d$ 的倍数。

由于这个数字可能很大，芙莉莲只关心这个数模 $10^9+7$ 之后的数值。

输入

一行两个整数，分别代表 $k$（$1 \le k \le 10^{10000}$）和 $d$（$1 \le d \le 100$）。

输出

一行一个整数表示所求的答案，注意答案要对 $10^9+7$ 取模。

样例

30
4

6

一共有 $6$ 个合法的数字：$4,8,13,17,22,26$ 。

98765432109876543210
58

635270834

来源

2025 UESTC ICPC Training for Dynamic Programming and Search