#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 5e3+, mod = 1e9+;

int f[N][N], g[N][N];

char s[N];

int lcp[N][N];

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

{

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

    else {

        int c = lcp[i][j];

        return s[i+c] > s[j+c];

    }

}

//#define LOCAL

int main()

{

#ifdef LOCAL

    freopen("in.txt","r",stdin);

#endif

    int n, i, j;

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

    if(s[] == ''){ puts(""); return ; }

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

        for(j = n; j > ; j--){

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

        }

    }

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

        for(j = ; j < i; j++) {

            g[i][j] = g[i][j-];

            if(s[i-j+] != ''){

                f[i][j] = g[i-j][min(j-,i-j)];

                if(f[i-j][j] && bigger(i-j+,i-j-j+,j)){

                    f[i][j] += f[i-j][j];

                    if(f[i][j] >= mod) f[i][j] -= mod;

                }

                g[i][j] += f[i][j];

                if(g[i][j] >= mod) g[i][j] -= mod;

            }

        }

        f[i][i] = ;

        g[i][i] = g[i][i-] + ;

        if(g[i][i] == mod) g[i][i] = ;

    }

    printf("%d\n",g[n][n]);

    return ;

}