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 

from imp import reload

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

#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

import decorator
#Help function remember it's real name. Good for debug.
#Doesn't work too, should use decorator module? Even it doesn't work for souce. Use __wrapped__ attribute. 
from functools import wraps
from decorator import decorate
from decorator import decorator as dec

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

@dec
def lfy(f,*a):
    return list(f(*a))
    return f(*a)

def _lfy(f,*a):
    return list(f(*a))

def lfy(f):
    return decorate(f,_lfy)


'''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

'''Words'''

def lsplit(l,n):
    return [l[n*i:n*(i+1)] for i in range(len(l)//n+1)]

def getwords(s):
    return book.smartsplit(s)

def iscap(s):
    return s[0]!=s[0].lower()

def islow(s):
    return s[0]==s[0].lower()

def low(s):
    return s.lower()


#Lems calculation takes 95% of time, so do it only once. 
def getlems(s,nocap=False):
    l=getwords(s)
    if nocap: l=lf(l,islow)
    else: l=lm(low,l)
        
    return lm(book.lem, l)

#Get sensts as lists. Sentsplit for strings? 
@lfy
def getsents(s):
    stops='.?!'
    l=book.smartsplit(s, save=stops)
    prev=0
    for i,x in enum(l):
        if x[-1] not in stops: continue
        x=x[:-1]
        yield(l[prev:i+1])
        prev=i+1

    
@lfy
def smartlems(s):
    l=sentsplit(s)
    for i,x in enum(l):
        for w in getlems(x,nocap=True): yield Str(w,ksent=i,lsent=l)
    pass


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)

#Wish-lists: add auto-trailing of exception. Show value and go to fucntions where program breaks.
#Also problems with things like: p,s=l. And l.append. Changes var, but we don't see how.  
#And things like '+=' and '-='.
#Also problems with decorators and internal functions in general.
#Also no yield processing. Also recursion problems. 

#We safely can add var there. Even if it's overwritten function remembers initial value. 
#And function is defined near the value. 
ndeb=200
def deb(f,v=None,n=ndeb):
    #Allow one variable or list of vars.
    if ist(v,str): v=[v]
    #Get source of inner function. 
    try: source=getsource(f.__wrapped__)
    except: source=getsource(f)
        
    l=source.split('\n')
    s=''; first=1
    for i,x in enum(l):
        
        line=strip(x)
        #Avoid comments and decorators? Yes, but add them to source. So you don't block decorator accidentally.
        #But then it breaks work of analyzers? 
        if not line or line[0] in '#@': 
            s+=row(x)
            continue
        
        #Avoid looking into long dicts
        if ('{' in x and '}' not in x):
            s+=row(x)
            continue
        gap=fa(' *',x)[0]
        #Turn string into code string (with indent and \n symbol). Works on function source.
        fcode=lambda x:gap+row(x)
        showcode=lambda x: fcode('print("code:{}\\n")'.format(strip(x)))
        
        #Print function name if it's a first inner line.
        if first and not line.startswith('def '): 
            first=0
            s+=fcode('print("Function: {}\\n")'.format(f.__name__))
            #Add f to source, to use it later. 
            s+=fcode('fcut=lambda x:str(x)[:{}]'.format(n))
        
        kwords=('for ','if ','else:','try:','except:','finally:')
        if any([strip(x).startswith(kw) for kw in kwords]):
            #Don't forget that slicing has it too, like "if x[1:]>3: y=x[1:]".
            bef,aft=x.split(':')
            if strip(aft)!='':
                s+=row(bef+':')
                #Don't forget to increase gap and strip new line.
                gap+=' '*4; x=gap+strip(aft)
            
        
        lvar=fa('(\w+)=[^=]',x)
        
        
        
        #Check if vars in debug vars? Check for none to allow giving v=[] as to show only return values. 
        #i>0 to avoid looking at default values of function. Better to check explicitly. Problem with inner f?
        if lvar and not line.startswith('def ') and (v==None or lvar[0] in v):
            var=lvar[0]

            #We can't use it cause x is var name, not value. deb runs before function itself. 
            #fcut=lambda x:str(x)[:n]
            
            #String for prev calculation. Don't override native prevs. Use _.
            sprev=coderows('try: _prev={};except: _prev="empty"'.format(var),gap)
            #Add prev and f calculation. 
            s+=sprev+row(x)
            #Show prev and next. Escape \n, so it wouldn't split function code.  
            s+=fcode('print("{0}:",fcut(_prev),"\\n->",fcut({0}))'.format(var))
            #Show function. We could have print it outside of function? 
            #No it should be activated when we go there, not when we replace the function. 
            s+=showcode(x)
        else: 
            #What function sends us? 
            if line.startswith('return '):
                #Dont' forget to use '+', so it would capture at least something. 
                #Use any sym to allow for list-generator. Allow any number of space betw return and value. 
                res=fa('return[ ]+(.+)',x)[0]
                s+=fcode('print("Returns",{})'.format(res))
                s+=showcode(x)
            s+=row(x)
        #Note that '\t' didn't work there. We use ' '*4. Print function
        #if strip(x)[:4]=='def ': s+=gap+' '*4+'print("Function: {}\\n")\n'.format(f.__name__)
        
        
 
    #Deals with functions from other modules. 
    #Takes values from global scope, uses it's own local namespace. Good to not pollute global one. 
    #Problem: wouldn't work for debug of inner function. Should use some temp variables? 
    #Maybe some hacks with namespace containers. Actually we make temp change to global vars. 
    print(source)
    print(s)
    #You should create dict for local namespace before hand?
    d={}; exec(s,fspace(f),d)
    return d[f.__name__]

#Deep deb. How can we place kw arguments without redefenition of defaults? 
#Works bad with decorated inner functions? 
def ddeb(f0,*a,f=None, v=None, n=ndeb):
    #Allow for shallow functions. Replace namespace anyway for recursive reasons. 
    if f==None:
        f=f0
        f0=deb(f0,v=v,n=n)
        
    name=f.__name__
    
    d=fspace(f)
    d[name]=deb(f,v=v,n=n)
    
    #Catch exception, but restore namespace afterwards.
    try: print('Full result:',f0(*a))
    finally: d[name]=f
    
n=input()
s=input()
print(s+'!')