C. RECOVER - Khôi phục dãy số

Sau một đêm cày game, Thắng vô cùng mệt mỏi và không thể tập trung nghe giảng. Hôm nay, thầy Hoà đã viết một dãy số nguyên dương tăng dần và cùng các bạn cố gắng tìm ra những tính chất đặc biệt của dãy số. Chuẩn bị sang bài mới, nhìn thấy Thắng gật gù, thầy Hòa xóa hết bảng và xuống kiểm tra. Thắng rất tự tin là đã chép bài đầy đủ. Tuy nhiên thầy đã phát hiện ra khi chép dãy số, Thắng láu cá không ghi thêm các dấu "," phân tách các số. Không thể nhớ nổi việc điền các dấu "," vào những vị trí nào, thầy Hòa yêu cầu Thắng đếm số lượng cách thêm dấu "," vào giữa các chữ số để được một dãy tăng.

Yêu cầu: Hãy giúp Thắng trả lời câu hỏi của thầy giáo đưa ra.

Dữ liệu vào:

• Một dòng duy nhất là xâu gồm các chữ số.

Dữ liệu ra:

• Ghi ra một số nguyên là số lượng cách thêm dấu "," vào giữa các chữ số để có được một dãy tăng theo yêu cầu của thầy. Do số lượng cách có thể rất lớn, thầy chỉ yêu cầu Thắng đưa ra kết quả lấy số dư trong phép chia cho .

Ví dụ:

Dữ liệu vào:

111

Dữ liệu ra:

2

Giải thích

• Có cách là:

Dữ liệu vào:

21023

Dữ liệu ra:

3

Giải thích:

• Có cách là:

Ràng buộc:

• Có số test tương ứng số điểm có ;
• Có số test khác tương ứng số điểm có ;
• Có số test khác tương ứng số điểm có ;
• Có số test khác tương ứng số điểm có .