Atcoder Educational DP Contest S - Digit Sum

View as PDF

Submit solution


Points: 0.30 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout

Suggester:
Problem source:
Atcoder Educational DP Contest
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Hãy đếm số lượng số nguyên (modulo ~10^9+7~) trong phạm vi từ ~1~ đến ~K~ (tính cả ~1~ và ~K~) thoả mãn:

  • Tổng các chữ số trong biểu diễn thập phân của số đó là bội của ~D~.

Input

Dòng thứ nhất chứa số nguyên ~K~ ~(1 \le K < 10^{10000})~.

Dòng thứ hai chứa số nguyên ~D~ ~(1 \le D \le 100)~.

Output

In ra số lượng số nguyên thoả mãn điều kiện, modulo ~10^9+7~.

Sample 1

Input
30
4
Output
6

Có ~6~ số nguyên thoả mãn điều kiện là: ~4,8,13,17,22~ và ~26~.

Sample 2

Input
1000000009
1

Hãy nhớ in ra đáp án chia lấy dư cho ~10^9+7~.

Output
2

Sample 3

Input
98765432109876543210
58
Output
635270834

Comments

Please read the guidelines before commenting.


There are no comments at the moment.