New Year and Ancient Prophecy

## 题目描述 给一个n位数，要求将该n位数拆分成若干数字，且需满足： - 数字的顺序要严格递增 - 数字都是正整数 - 没有前导零 求所有可能的方案数 ## 输入格式 输入第一行包含一个整数n(1<=n<=5000)，表示所给数字的位数 第二行包含一串长度等于n的数字。保证第一个数字不是0 ## 输出格式 输出正确拆分的方案数模1e9+7 ## 说明 在第一个样本中有8种方法： “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” 请注意，“123434”=“12”+“34”+“34”不算方案数，因为数字必须严格增加。 在第二个样本中有4种方式： “20152016”=“20152016” “20152016”=“20”+“152016” “20152016”=“201”+“52016” “20152016”=“2015”+“2016”

Limak is a little polar bear. In the snow he found a scroll with the ancient prophecy. Limak doesn't know any ancient languages and thus is unable to understand the prophecy. But he knows digits! One fragment of the prophecy is a sequence of $ n $ digits. The first digit isn't zero. Limak thinks that it's a list of some special years. It's hard to see any commas or spaces, so maybe ancient people didn't use them. Now Limak wonders what years are listed there. Limak assumes three things: - Years are listed in the strictly increasing order; - Every year is a positive integer number; - There are no leading zeros. Limak is going to consider all possible ways to split a sequence into numbers (years), satisfying the conditions above. He will do it without any help. However, he asked you to tell him the number of ways to do so. Since this number may be very large, you are only asked to calculate it modulo $ 10^{9}+7 $ .

The first line of the input contains a single integer $ n $ ( $ 1<=n<=5000 $ ) — the number of digits. The second line contains a string of digits and has length equal to $ n $ . It's guaranteed that the first digit is not '0'.

Print the number of ways to correctly split the given sequence modulo $ 10^{9}+7 $ .

6
123434

8

8
20152016

4

In the first sample there are $ 8 $ ways to split the sequence: - "123434" = "123434" (maybe the given sequence is just one big number) - "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" Note that we don't count a split "123434" = "12" + "34" + "34" because numbers have to be strictly increasing. In the second sample there are $ 4 $ ways: - "20152016" = "20152016" - "20152016" = "20" + "152016" - "20152016" = "201" + "52016" - "20152016" = "2015" + "2016"