Preparando MOJI
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:
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 109 + 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 109 + 7.
6
123434
8
8
20152016
4
In the first sample there are 8 ways to split the sequence:
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:
Informação
Provedor Codeforces
Código CF611D
Tags
Submetido 0
BOUA! 0
Taxa de BOUA's 0%
Datas 09/05/2023 09:02:57
Relacionados