Limak 是一只小北极熊。他在雪地里发现了一卷写着古老预言的卷轴。利马克不懂任何古代语言,因此无法理解这个预言。但他认识数字!
预言的一个片段是一系列 n 个数字。第一个数字不为零。利马克认为这是一些特殊年份的清单。很难看到任何逗号或空格,所以也许古人没有使用它们。现在利马克想知道那里列出的是哪一年。
Limak 假设三件事:
- 年份按严格递增的顺序列出;
- 每年都是一个正整数;
- 没有前导零。
Limak 将考虑将序列拆分为数字(年)的所有可能方法,满足上述条件。他会在没有任何帮助的情况下做到这一点。然而,他要求你告诉他有多少种方法可以做到这一点。由于这个数字可能非常大,因此只要求您计算它对 109 + 7 求模。
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 5000) — 位数。
第二行包含一串数字,长度等于 n。保证第一位不是“0”。
输出
打印以 109 + 7 为模正确分割给定序列的方法数。
示例
输入 #1
6 123434
输出 #1
8
输入 #2
8 20152016
输出 #2
4
注意
在第一个示例中,有 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"