Bài toán cắt xâu số thành các số tăng nghiêm ngặt: cho xâu ~S~ chỉ gồm ký tự '0'..'9'. Hãy đếm số cách cắt ~S~ thành các đoạn liên tiếp ~S_1+S_2+\dots+S_k~ ~(k>0)~ sao cho mỗi đoạn khi diễn giải là một số thập phân không có số 0 ở đầu và dãy các số này tăng nghiêm ngặt.

Yêu cầu

Cho xâu ~S~ chỉ gồm ký tự '0'..'9'. Đếm số cách tách ~S=S_1+S_2+\dots+S_k~ ~(k>0)~ thoả mãn:

• Ký tự đầu tiên của mỗi ~S_i~ khác '0' ~(i=1..k)~.
• Khi coi ~S_i~ là giá trị số nguyên dương ở cơ số 10, dãy ~S_1,S_2,\dots,S_k~ tăng nghiêm ngặt.

Kết quả lấy theo modulo ~10^9+7~.

Dữ liệu

• Một dòng duy nhất chứa xâu ~S~ không bắt đầu bằng '0', với ~1\le |S|\le 5000~.

Kết quả

• Một số nguyên là số cách cắt thoả mãn, tính theo modulo ~10^9+7~.

Ví dụ

Ví dụ 1

Input

112323

Output

5

Ví dụ 2

Input

10203

Output

2

Giải thích

Ví dụ 1

Các cách hợp lệ của ~S=\text{"112323"}~ là:

• ~\text{"1"}+\text{"12"}+\text{"323"}~
• ~\text{"1"}+\text{"12323"}~
• ~\text{"11"}+\text{"2323"}~
• ~\text{"112"}+\text{"323"}~
• ~\text{"12323"}~

Ví dụ 2

Với ~S=\text{"10203"}~, các cách hợp lệ:

• ~\text{"10"}+\text{"203"}~
• ~\text{"10203"}~ Lưu ý: các đoạn không được bắt đầu bởi '0', do đó tách kiểu ~\text{"1"}+\underbrace{\text{"02"}}_{\text{không hợp lệ}}+\text{"03"}~ bị loại.

Gợi ý (có thể đúng hoặc sai)

• 100% số điểm cho lời giải ~\mathcal{O}(n^2)~ với ~n=|S|\le 5000~, dựa trên:
  • So sánh hai số dạng xâu ~X,Y~: nếu ~|X|\ne |Y|~ thì số có độ dài lớn hơn là lớn hơn; nếu bằng nhau, so sánh từ trái sang phải. Để tối ưu so sánh khi ~|X|=|Y|~, tiền xử lý bảng LCP (Longest Common Prefix) giữa mọi cặp vị trí trong ~S~ bằng kỹ thuật Z/Suffix và quy hoạch động, cho phép so sánh hai đoạn độ dài bằng nhau trong ~\mathcal{O}(1)~.
  • Quy hoạch động theo điểm cắt cuối: đặt ~\mathrm{dp}[i]~ là số cách cắt tiền tố ~S[1..i]~ kết thúc bằng một đoạn cuối ~S[j..i]~ ~(1\le j\le i, S[j]\ne '0')~; khi xét hai đoạn liên tiếp ~S[t..j-1]~ và ~S[j..i]~, điều kiện tăng nghiêm ngặt kiểm bằng quy tắc so sánh ở trên. Có thể tổ chức theo độ dài đoạn cuối và dùng tổng luỹ tích để giảm từ ~\mathcal{O}(n^3)\to\mathcal{O}(n^2)~.
  • Lấy modulo ~10^9+7~ ở mọi phép cộng.
• Mẹo triển khai:
  • Tiền xử lý ~\mathrm{LCP}[i][j]~ cho mọi cặp vị trí ~i<j~ bằng kỹ thuật Z trên từng suffix (hoặc chuẩn bị mảng Z/Kasai tuỳ chọn), bộ nhớ ~\sim n^2~ với ~n=5000~ vẫn chấp nhận được trong giới hạn thi (~\approx 25\,\text{triệu}~ số nguyên). Có thể tối ưu bộ nhớ bằng so sánh trực tiếp khi độ dài nhỏ.</li>
  • Khi so sánh ~S[a..b]~ và ~S[c..d]~ có cùng độ dài ~\ell~, nếu ~\mathrm{LCP}[a][c]\ge \ell~ thì hai đoạn bằng nhau (không chấp nhận vì cần tăng nghiêm ngặt); ngược lại so ký tự ngay sau LCP để quyết định lớn/nhỏ.