样例下载

问题描述

考古学家小 Z 最近找到了一些古老的文字，那上面竟然有阿拉伯数字！经过小 Z 的一系列研究，他发现这些数字是古人用来记录日期的，但是这些数字中间没有分隔符，于是小 Z 想知道这些数字到底记录了多少日期。凭借着他多年考古的经验，他可以肯定以下三点：

1. 所有日期按照从左到右的顺序是严格递增的。
2. 每个日期都是一个正整数。
3. 所有日期都不含前导 0。

因此，这一串数字也是不含前导 0 的。小 Z 想知道，有多少种添加分隔符的方式，使得分割后的每个日期都满足上述的三条要求。由于这个数字过于庞大，你只需要告诉他答案对 $10^9 + 7$ 取模的结果就可以了。

输入

输入的第一行为一个正整数 n，表示这串数字的长度。

接下来的一行为一个长度为 n 的数字串，保证该数字串没有前导 0。

输出

输出一行一个整数，表示分割方案数对 $10^9 + 7$ 取模的结果。

输入输出样例 1

Input

6
123434

Output

8

输入输出样例 2

Input

8
20152016

Output

4

输入输出样例 1 解释

共有 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” 是不合法的，因为有两个串 “34” 是相等的。

数据规模及约定

对于所有的测试用例，保证有 1 ≤ n ≤ 5 000。

本题共有 4 个子任务，对于每个子任务，你必须要通过该子任务下的所有测试点才能获得该子任务的全部分数，否则不得分。子任务说明见下：