Limak is a little polar bear. In the snow he found a scroll with the ancient prophecy. Limak doesn't know any ancient languages and thus is unable to understand the prophecy. But he knows digits!

One fragment of the prophecy is a sequence of *n* digits. The first digit isn't zero. Limak thinks that it's a list of some special years. It's hard to see any commas or spaces, so maybe ancient people didn't use them. Now Limak wonders what years are listed there.

Limak assumes three things:
 -  Years are listed in the strictly increasing order; -  Every year is a positive integer number; -  There are no leading zeros. 
Limak is going to consider all possible ways to split a sequence into numbers (years), satisfying the conditions above. He will do it without any help. However, he asked you to tell him the number of ways to do so. Since this number may be very large, you are only asked to calculate it modulo 10<sup class="upper-index">9</sup> + 7.
The first line of the input contains a single integer *n* (1 ≤ *n* ≤ 5000) — the number of digits.

The second line contains a string of digits and has length equal to *n*. It's guaranteed that the first digit is not '0'.
In the first sample there are 8 ways to split the sequence:
 -  "123434" = "123434" (maybe the given sequence is just one big number) -  "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" 
Note that we don't count a split "123434" = "12" + "34" + "34" because numbers have to be strictly increasing.

In the second sample there are 4 ways:
 -  "20152016" = "20152016" -  "20152016" = "20" + "152016" -  "20152016" = "201" + "52016" -  "20152016" = "2015" + "2016"
from collections import OrderedDict
from collections import deque
import time
import random
import sys
import re 

def sizeof(t):
    return sys.getsizeof(t)

def pr(x):
    print(x)

def ti():
    return time.time()

#Function profiler. Sorting options: 0-by call number, 1-by function inner time, 2-by function cumulative time.
def profile(s,sort=1):
    import cProfile
    cProfile.run(s,sort=sort)

#Use @initializer wrapper. Checks for defaults existence. Why do we need to go in reverse direction? 
#How much slower it is than usual init? 
from functools import wraps
import inspect

def inize(fun):
    names, varargs, keywords, defaults = inspect.getargspec(fun)
    @wraps(fun)
    def wrapper(self, *args, **kargs):
        self.inited=False
        for name, arg in list(zip(names[1:], args)) + list(kargs.items()):
            setattr(self, name, arg)
        
        if defaults:
            for i in range(len(defaults)):
                index = -(i + 1)
                if not hasattr(self, names[index]):
                    setattr(self, names[index], defaults[index])
        fun(self, *args, **kargs)
        self.inited=True
    return wrapper

#To avoid problems with default empty lists.
def denone(fun):
    def wrap(*args,**kws):
        largs=inspect.getargspec(fun)[0]
        if largs[-1] not in kws and len(args)<len(largs): kws[largs[-1]]=[]
        return fun(*args, **kws)
    return wrap

def fread(s):
    return open(s,'r').read()

def hardread(s):
     return open(s,'r',encoding="utf8").read()

def fwrite(f,s):
    return open(f,'w',encoding="utf8").write(s)

#Helper functions zone. 

def tel(n=5):
    return [i+1 for i in range(n)]

def tel2(n=4,m=None):
    if m==None: m=n
    return [[i*m+j+1 for j in range(m)] for i in range(n)]

def tels(n=5):
    return 'abcde'*2

def abc(n):
    return list(map(chr, range(97, 123)))[n]


'''Operations'''

def lflat2(l):
    if ist(l[0], list): return [x for y in l for x in y]
    else: return l
    
def lflat(l):
    return lflat2(l)

def lflat(l):
    nl=[]
    for x in l:
        if (isiter(x)): 
            nl+=lflat(x) 
        else: 
            nl.append(x)
    return nl

def ist(o,t):
    return isinstance(o,t)

def antinone(l):
    if l==None: return []
    else: return l
    
def getl(f):
    return f().split()

def getint(f):
    return int(f())

def getints(s):
    return lm(int, s.split())

def stoints(s):
    return lm(int, s.split())

def enum(l):
    return enumerate(l)

def sign(x):
    if x>0: return 1
    if x<0: return -1
    return 0

global la
la={
    '^': lambda x,y:x**y,
    '**':lambda x,y:x**y,
    '+': lambda x,y:x+y,
    '-': lambda x,y:x-y,
    '*': lambda x,y:x*y,
    '/': lambda x,y:x/y,
    '//': lambda x,y:x//y,
    '%': lambda x,y:x%y,
    '1': lambda x,y:x,
    '2': lambda x,y:y,
    '>': lambda x,y:x>y,
    '=>':lambda x,y:x>=y,
    '<': lambda x,y:x<y,
    '<=': lambda x,y:x<=y,
    '!=': lambda x,y:x!=y,
    '==': lambda x,y:x==y,
    'in': lambda x,y:x in y,
    'nin': lambda x,y:x not in y,
    'and': lambda x,y:x and y,
    'or': lambda x,y:x or y,

}


#Shortcut-functions processor. Allow fixing of the second arg. 
def tof(f,a2=None):
    if ist(f,str): f=la[f]
    return f if not a2 else lambda x:f(x,a2)

def isiter(o):
    try:
        iterator = iter(o)
    except TypeError:
        return 0
    else:
        return 1

def isarray(o):
    if isiter(o) and not ist(o,str): return 1
    else: return 0    

def lm(f,*l):
    f=tof(f)
    return list(map(f,*l))

#Multifunction
def mf(f,*l):
    return lm(f,l)

def fitem(i=0):
    return lambda x:x[i]

fself=lambda x:x

def lf(l,f):
    return [x for x in l if f(x)]


def lzip(*l):
    return list(zip(*l))

#fzip('+', [1,2,3])=6. Problem: list doesn't change? You shouldn't copy it, choose indeces instead. 
#Note! It takes list of arguments, not tuple!
def fzip(f,l):
    f=tof(f)
    for i in range(1,len(l)):
        l[i]=f(l[i-1],l[i])
    return l[-1]
        
def allwith(s,l):
    return [x for x in l if s in x]

class Op:  
    def __init__ (self,l=None):
        self.l=l
    
    def __add__(self,s):
        return self.act('+',s)
    
    def __sub__(self,s):
        return self.act('-',s)
    
    def __mul__(self,s):
        return self.act('*',s)
    
    def __truediv__(self,s):
        return self.act('/',s)
    
    def __pow__(self,s):
        return self.act('**',s)
    
    def __lt__(self,s):
        return self.act('<',s)
        
    def __gt__(self,s):
        return self.act('>',s)
        
    def __le__(self,s):
        return self.act('<=',s)
        
    def __ge__(self,s):
        return self.act('>=',s)
    
    def __eq__(self,s):
        op='in' if isiter(s) else '=='
        return self.act(op,s)
        
    def __ne__(self,s):
        op='nin' if isiter(s) else '!='
        return self.act(op,s)

class oneof(Op): 
    def act(self,op,s):
        l=[tof(op)(x,s) for x in self.l]
        return fzip('or',l)

class allof(Op):   
    def act(self,op,s):
        l=[tof(op)(x,s) for x in self.l]
        return fzip('and',l)
        
class lif(Op):
    @inize
    def __init__(c,l,key=fself): pass
    
    #key acts on values before filtering. 
    def act(self,op,y):
        return lf(self.l, lambda x:tof(op)(self.key(x),y))   
    
#Super lambda. But what if there are several variables? No complex statements lik X**2+10?
class X(Op):
    def act(c,op,y):
        return tof(op,y)

X=X()

#Eg lop(l)*3
class lop(Op):
    def act(self,op,y):
        f=tof(op)
        return [f(x,y) for x in self.l]

'''Dicts and lists'''    

#Transpose table.
def ltrans(l):
    return [[x[k] for x in l] for k in range(0,len(l[0]))]

class D(dict):
    def __init__(c,d):
        dict.__init__(c,d)
        for x in d:
            setattr(c,x,d[x])  
        
    def __setattr__(c,x,v):
        c.__dict__[x]=v
        c[x]=v
        
#New array with specific dimensions. 
def lnew(*n,fill=0):
    l=[]
    for i in range(n[0]):
        if len(n)>1: l.append(lnew(*n[1:],fill=fill))
        else: l.append(fill)
    return l
        

#Fast dict from list. Works for words list to, cause maintains unique keys.
#Problem with empty list, binded to function. 
def dnew(l, fill=0):
    d={}
    for x in l: d[x]=fill
    return d

def dlnew(l):
    d={}
    for x in l: d[x]=[]
    return d

def odnew(l=None, fill=0):
    d=OrderedDict()
    if not l: return d
    
    for x in l: d[x]=fill
    return d

def odlnew(l=None):
    d=OrderedDict()
    if not l: return d
    
    for x in l: d[x]=[]
    return d


def dfill(d,fill):
    for x in d: d[x]=fill
    return d

def combzip(l1,l2):
    return [(x,y) for x in l1 for y in l2]

#Place numbers in ascending order. Maybe better to use yield?  
def comb(state,k,n,l):
    p=len(state)
    if p==k: l.append(lm(int,state))
    else:
        prev=int(state[-1]) if state!=[] else -1
        for x in range(prev+1,n-k+p+1):
            comb(state+[x],k,n,l)
        
def combs(k,n):
    l=[]
    comb([],k,n,l)
    return l

def lcomb(state,k,l,lbase):
    p=len(state)
    if p==k: l.append(lm(int,state))
    else:
        for x in lbase: lcomb(state+[x],k,l,lbase)
        
def lcombs(lbase,k):
    l=[]
    lcomb([],k,l,lbase)
    return l

from itertools import product
def lcombs(l,k):
    return product(l,repeat=k)

def clad(c):
    return c.__dict__

def saferec(x):
    return 1/x if x!=0 else float('inf')

def safef(f,*x):
    try:
        return f(*x)
    except: return x
    
#Isn't possible!
def safev(x):
    try: return x
    except: return 'Hey!'
    return
   

#Real copy of dict to avoid iterating over changing structure
def dits(d):
    return list(d.items())

def fastd(l):
    return {x[0]:x[1:] for x in l}

def bifind(l,v,key=fself):
    #Note that assignemt to var makes it innermost local.
    def f(k,n):
        
        #Take the closest lower item. 
        if k>=n: 
            if key(l[k])>v and k!=0:k-=1
            return k
        
        i=(k+n)//2; x=key(l[i])
        
        if x==v: return i
        if v<x: return f(k,i-1)
        else: return f(i+1,n)
        
    n=len(l); k=0
    return l[f(k,n-1)]

def idict(l):
    return {x[0]:[i]+x[1:] for i,x in enum(l)}

#Table indexer. Takes table and column number. Returns sorted and indexed list based on this column.
def lindex(l,k):
    l.sort(key=lambda x:x[k],reverse=True)
    #Adds index column. list(x) operation handles one-dimensional table.
    for i,x in enumerate(l): l[i]=[i+1]+list(x)
    return l

def fitem(i):
    return lambda x:x[i]

def tabsort(l,k=0,rev=1):
    return sorted(l,key=fitem(k),reverse=rev)

def safedit(d,k,safe=0):
    return d[k] if k in d else safe
    

def antific(s):
    s=s.replace('”',"'")
    s=s.replace('“',"'")
    s=s.replace('…','...')
    return s

def lfy(f):
    def wrap(*a):
        return list(f(*a))
    return wrap

'''Classes'''

#Needs new to initialize str or int children
class Str(str):
    def __new__(c,s,**kw):
        obj = str.__new__(c, s)
        
        for k in kw:
            obj.__dict__[k]=kw[k]
        return obj
    
class L(list):
    @inize
    def __init__(c,l=None,*a,**kw):
        if l==None: l=[]
        init(c,l)
        
def getpar(c):
    return c.__class__.__bases__[0]

#Would be problem with grandfather class in vertical chain of calls.  
#That's why we create spec variable to track class in this multi-level process.
def autoclass(f):
    def wrap(c,*args): 
        #Note that _par is class, not instance, that's why getpar doesn't work there.
        par=c._par.__bases__[0] if '_par' in c.__dict__ else getpar(c)
        c._par=par
        f(c,*args)
        #Don't forget to kill variable at the end.
        if '_par' in c.__dict__: del(c._par)
    return wrap

@autoclass
def init(c,*args):
    c._par.__init__(c,*args)
    
@autoclass
def parcall(c,*args):
    return c._par.__call__(c,*args)

@autoclass
def parset(c,*args):
    return c._par.__setattr__(c,*args)

def revbool(b):
    if b: b=False
    else: b=True
    return b

def fa(p,s):
    return re.findall(p,str(s),re.DOTALL)

#Doesn't take last part. 
def spliton(s,chars):
    return fa('.*?[{}]'.format(chars),s)
    
def skick(s,sub):
    return ''.join(s.split(sub))

def strip(s):
    return s.strip()

def sentsplit(s):
    s=skick(s,'\n')
    l=spliton(s,'.?!')
    l=lif(l)!=''
    l=lm(strip,l)
    
    return l

from inspect import getsource

def pr(x):
    return print(x)

def row(s):
    return s+'\n'

def coderows(s,gap):
    return ''.join([gap+row(x) for x in s.split(';')])

#Look at module where function is defined. Take space of this module. 
def fspace(f):
    mod=f.__module__
    if mod=='__main__': dglob=globals()
    else: dglob=globals()[mod].__dict__
    return dglob

def split(s,c):
    return s.split(c)
    
def intjoin(l):
    return int(''.join(lm(str,l)))

#Actually you don't need variable k2, that's artifact of a mistake: forgetting about gluing prohibition in S calc.
#Leave it for demonstration purposes.
#Maybe it can auto-detect types based on your inputs? Or explicit types easier to read? 
def checkS(n,*k,t):
    p=lnew(3)
    #Pos of values.  
    p[0]=n-k[0]+1
    for i in range(1,3): p[i]=p[i-1]+k[i-1]
    
    #Values of all active elements in checking. 
    v=[intjoin(V[p[i]:p[i]+k[i]]) for i in range(3)]
    
    #Anti-leadzero. 
    if V[p[1]]==0: return 0
    
    #Type 1:..llk. Type 2: l(l-k)k. 
    if t==1 and v[1]>v[0]: return 0
    
    #Problem: you need not sum values, but join them? Don't confuse string addition with integer one. 
    #So maybe intjoin was bad idea? 
    if t==2 and intjoin((v[1],v[2]))<=v[0]: return 0
    return fS(n,k[0])

#Main function for processing combs of different classes. 
#For first two types k2=1. 
def sumS(n,k2,t): 
    #Case of ..kk1. Start from 1. Use S to count combs. 
    if t==1: 
        #Can we make spec-function for these types of tasks? Unlimited for? 
        su=0
        for k0 in count(1):
            #If this configuration exceeds substring size. 
            if 2*k0+1>n: break
            su+=checkS(n-k0-1,k0,k0,1,t=1)
        return su
    
    #Case of ..k(k-1)1. Start from 2.
    if t==2:
        su=0
        for k0 in count(2):
            if 2*k0>n: break
            su+=checkS(n-k0,k0,k0-1,1,t=2)
        return su
    
    #Case of ..lk with l<=k. Look with caution at ..kk case. 
    if t==3:
        #Problem: Case with n==k. Add spec condition.
        if n==k2: return 1
        if V[n-k2+1]==0: return 0
        
        su=0
        for k1 in range(1,k2+1): 
            if k1+k2>n: break
            if k1==k2:
                #Problem: didn't work when k+k>n. Note that l+k can be >n too. That's why we added break before. 
                v1,v2=mf(intjoin, V[n-2*k2+1:n-k2+1], V[n-k2+1:n+1])
                if v1>=v2: break
            su+=fS(n-k2,k1)
        return su

from inspect import currentframe, getframeinfo, getouterframes, stack, getargvalues
#Print sum pieces. 
def talksum(*x,nodeb=0):
    #print(getframeinfo(currentframe()))
    #print(getouterframes(currentframe())[1])
    
    #Stack getter is too slow, use only in debug. 
    if nodeb: return sum(x)
    prevframe=stack()[1]
    #Give it a frame object. 
    prevargs=getargvalues(prevframe[0])
    
    print('Function:',stack()[1][3], prevargs.locals,'Elements:', x, 'Res:', sum(x))
    return sum(x)
        
def fN(n):
    if N[n]!=-1: return N[n]
    #Check not-glued case
    noglue=all([V[i+1]>V[i] for i in range(1,n)])
    #N[n]=N[n-1]+int(noglue)+sumS(n,1,1)+sumS(n,1,2)
    
    #Note that we give it fN to launch recursion, not N. 
    N[n]=talksum(fN(n-1),int(noglue),sumS(n,1,1),sumS(n,1,2),nodeb=1)
    return N[n]
    
def fS(n,k):
    if S[n][k]!=-1: return S[n][k]
    S[n][k]=sumS(n,k,3)
    return S[n][k]      
    
def Nnumstairs(s):
    if len(s)==1: return 1
    
    #Init empty functions cells and recursion seeds. 
    global N,S,V
    V=[None]+lm(int,s)
    n=len(s); N=lnew(n+1,fill=-1); S=lnew(n+1,n+1,fill=-1)
    N[1]=1; S[1][1]=1
    
    return fN(n)

n=input()
s=input()

#ddeb(Nnumstairs,'23',f=checkS)#('123434')
print(Nnumstairs(s))


