Cho số nguyên dương \(n\), hãy cho biết trong phạm vi từ \(1\) tới \(n\) có bao nhiêu số nguyên dương có tổng các chữ số đúng bằng tổng các chữ số của \(n\) (xét trong biểu diễn thập phân)

Ví dụ với \(n=210\), tổng các chữ số của \(210\) là \(3\). Có \(9\) số trong phạm vi từ \(1\) tới \(210\) có tổng các chữ số bằng \(3\) là: \(3, 12, 21, 30, 102, 111, 120, 201, 210\)

Input

• Số nguyên dương \(n \leq 10^{300}\).

Output

• Số nguyên là kết quả tìm được, lấy phần dư khi chia cho \(10^9\).

Example

210

9