Tổng Chữ Số Chia Hết

Với một số nguyên không âm, tổng chữ số là tổng các chữ số trong biểu diễn thập phân của số đó.

Cho số nguyên dương $K$ có thể rất dài và số nguyên $D$. Hãy đếm các số nguyên $x$ thỏa $1\le x\le K$ và tổng chữ số của $x$ chia hết cho $D$. Vì kết quả có thể lớn, hãy lấy phần dư theo $1,000,000,007$.

Input

• Dòng đầu chứa số nguyên dương $K$ dưới dạng chuỗi.
• Dòng thứ hai chứa $D$.

Output

• In số lượng số thỏa mãn modulo $1,000,000,007$.

Constraints

• $1\le K<10^{10000}$.
• $1\le D\le 100$.
• $K$ không có số $0$ ở đầu.

Scoring

• Subtask $1$ ($50$ điểm): $K\le 10^5$.
• Subtask $2$ ($50$ điểm): Không có giới hạn bổ sung.

Example

20
2

10