CF611D.New Year and Ancient Prophecy

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 109 + 7.

Limak 是一只小北极熊。他在雪中发现了一卷记载着古老预言的卷轴。Limak 不认识任何古代语言，因此无法理解这则预言。但他认识数字！

预言的一段残片是由 $n$ 个数字组成的序列，且第一个数字不为零。Limak 认为这是一份特殊年份的列表。由于难以辨认其中的逗号或空格，或许古人根本未使用这些分隔符。现在，Limak 想知道这段序列究竟列出了哪些年份。

Limak 假设了以下三点：

• 年份按严格递增的顺序列出；
• 每个年份都是一个正整数；
• 每个年份不含前导零（即不能以 0 开头）。

Limak 打算独立考虑所有满足上述条件的、将该数字序列分割为若干数字（即年份）的方式。不过，他请你告诉他这样的分割方式总数是多少。由于该数目可能非常大，你只需计算其对 $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'.

输入的第一行包含一个整数 $n$（$1 ≤ n ≤ 5000$）—— 表示数字的位数。

第二行包含一个长度为 $n$ 的数字字符串。保证第一个数字不是 '0'。

Print the number of ways to correctly split the given sequence modulo 109 + 7.

输出将给定序列正确分割的方法数，对 $10^9 + 7$ 取模。

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"

在第一个样例中，共有 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”