#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cmath>

#include<cstdlib>

#include<vector>

#include<queue>

using namespace std;

typedef long long LL;

const int maxn=;

const int mod=1e9+;

int dp[maxn][maxn];

int f[maxn][maxn];

char s[maxn];

bool cmp(int i,int j,int len)

{

    if(f[i][j]>=len)return false;

    return s[i+f[i][j]]<s[j+f[i][j]];

}

int main()

{

    int n;

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

    for(int i=n; i>; --i)

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

            if(s[i]==s[j])f[i][j]=f[i+][j+]+;

    int ans=;

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

    {

        int sum=;

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

        {

            if(s[i]=='')

                dp[i][j]=;

            else if(i==)dp[i][j]=;

            else

            {

                int len=j-i+;

                bool flag=;

                if(i-len>=&&cmp(i-len,i,len))

                {

                    flag=;

                    sum=(sum+dp[i-len][i-])%mod;

                }

                dp[i][j]=sum;

                if(!flag&&i-len>=) sum=(sum+dp[i-len][i-])%mod;

            }

            if(j==n)ans=(ans+dp[i][j])%mod;

        }

    }

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

    return ;

}