/*

题意：给一个长度不超过5000的字符串，每个字符都是0到9的数字。

要求将整个字符串划分成严格递增的几个数字，并且不允许前导零。

思路：

1.很开心得发现，当我在前i个区间以后再加一个区间的时候，转移

的条件只跟最后一个区间的数字大小有关，这决定这道题可以dp...

2.dp[i][j]代表前j个字符，最后划分的区间的第一个字符是第i个的答案数。

3.可知对于所有的dp[i][i...n]他们的答案都取决与dp[1...i-1][i-1].

4.很容易想到对于同一个i，累加求得dp[i][k]的值，但是如何判断

数字大小呢...首先长度不同的情况下直接根据长度判断即可（因为不允许

前导零）。长度相同的情况下，需要比较这两个字符串哪个大。这个时候

预处理出  ook[i][j]代表以第i个位置和第j个位置为开头的两个字符串他嗯

第一个不相同的字符的位置。

*/

// 2016/9/6 13:07

#include<bits/stdc++.h>

#define N 5005

using namespace std;

int ook[][];

long long dp[N][N];

long long mod=1e9+;

char jilu[N];

int main()

{

    int n;

    scanf("%d%s",&n,jilu+);

    memset(ook,0x3f,sizeof(ook));

    for(int i=;i<=n;i++){

        for(int j=;j<=n;j++){

            if(jilu[i]!=jilu[j]){

                int k=;

                while(i-k>&&j-k>&&ook[i-k][j-k]>k){

                    ook[i-k][j-k]=k;

                    k++;

                }

            }

        }

    }

    for(int i=;i<=n;i++){

        if(jilu[i]=='')continue;

        long long sum=;

        int a=i-,b=i;

        while(b<=n){

            if(i==){

                dp[i][b]=;

            }

            else{

                while(a>&&i-a<b-i+){

                    sum+=dp[a][i-];

                    sum%=mod;

                    a--;

                }

                if(a>&&ook[a][i]<=b-i&&jilu[a+ook[a][i]]<jilu[i+ook[a][i]]){

                    sum+=dp[a][i-];

                    sum%=mod;

                    a--;

                }

                dp[i][b]=sum;

            }

            b++;

        }

    }

    long long ans=;

    for(int i=;i<=n;i++){

        ans+=dp[i][n];

        ans%=mod;

    }

    printf("%lld\n",ans);

}