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:
BJMinhNhut
Problem source:
Atcoder Educational DP Contest
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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.


  • -2
    Hinataa  commented on Sept. 25, 2024, 3:56 a.m.

    Cho em hỏi sao 2 test cuối là trường hợp gì mà sai v ạ


    • -4
      buitrunghieu  commented on Sept. 30, 2024, 8:04 a.m. ← edited

      Cảnh báo spoiler:

      Cai mod -1 di b sai, + mod len roi % lan nua la dc