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