Cech là giám đốc kho bạc của nước PoHub. Trong nhà ông có một chiếc két điện tử chứa rất nhiều tiền, được mở bằng cách nhập từng số (nhỏ hơn 5x105), rồi ấn NEXT, sau khi nhập xong hết các số thì ấn ấn OPEN.  Vì hay quên nên ông đã ghi lại mật mã két, chỉ có điều là viết liền tất cả các số lên một mảnh giấy. VD: mật mã là gồm 4 số “123” “456” “78” “912345” thì số trên mảnh giấy sẽ là 12345678912345. Hoặc mật mã gồm 3 số “1234” “5678” “912345” thì số trên mảnh giấy cũng sẽ là 12345678912345.

Ông tự hỏi với số được viết trên mảnh giấy thì có bao nhiêu cách “cắt” số đó ra thành các số để được một mã két.

Biết rằng mã két được tạo ra theo quy tắc:

+) Không có số nào bắt đầu bằng chữ số 0.

+) Số sau luôn lớn hơn số trước.

+) Tất cả các số đều là số nguyên dương.

Với IQ 690, ông đã có câu trả lời một cách rất nhanh chóng. Còn các bạn thì sao?

Dữ liệu ra: 

Một số duy nhất là số cách cắt số đó ra thành các số để được một mã két, mod 10^9 + 7

Inp1:

6

123434

Out1:

8

Inp2:

8

20152016

Out2:

4

Trong ví dụ 1: có 8 cách “cắt”

• "123434" : "123434" 

• "123434" : "1" ; "23434"

• "123434" : "12" ; "3434"

• "123434" : "123" ; "434"

• "123434" : "1" ; "23" ; "434"

• "123434" : "1" ; "2" ; "3434"

• "123434" : "1" ; "2" ; "3" ; "434"

• "123434" : "1" ; "2" ; "3" ; "4" ; "34"

Cách chia "123434" : "12" ; "34" ; "34" không được chấp nhận do số sau không lơn hơn số trước

 

Trong ví dụ 2: có 6 cách “cắt”

• "20152016" : "20152016"

• "20152016" : "20" ; "152016"

• "20152016" : "201" ; "52016"

• "20152016" : "2015" ; "2016"