In the year 2222, humanity discovered life on a planet outside the Milky Way and brought a cell back to Earth. After repeated research, humanity has fully mastered the developmental laws of this type of cell:

The initial form of the cell is "rod-shaped," with a head at one end, a tail at the other, and a trunk in between. Inside the cell is a sequence of codes (which you can think of as the DNA of this cell). The code is a string of digits of length $n$, containing only the digits $1$ to $9$, arranged along the trunk from head to tail.

First, the cell undergoes a primary division. The cell divides along the trunk into several spheres, and the trunk degenerates into filaments connecting adjacent spheres. During the division process, the mass is distributed uniformly. In other words, if it divides into $k$ spheres, the mass of each sphere is $1/k$ of the original. However, the distribution of the code is uncertain. If divided into $k$ spheres, the code is cut into $k$ segments (each segment having a length of at least $1$) and distributed among the spheres in order from head to tail. The figure below shows one valid primary division:

Next, the cell undergoes a secondary division. For each sphere, it contains a small segment of the code (note that it is ordered), which we treat as a decimal number $T$. This sphere will be divided into $T$ smaller spheres, arranged in a row and connected by the filaments formed from the degenerated trunk. The mass remains uniformly distributed, with each small sphere having a mass of $1/T$ of the original sphere. At this point, the code has served its purpose and disappears. The figure below shows the secondary division:

Finally, the cell undergoes mutation. The filaments between adjacent small spheres may degenerate, and these two small spheres will then be directly connected by tangency. Obviously, after the secondary division, every small sphere except for the two at the ends has two filaments connected to it (the small spheres at the head and tail ends have only one filament connected to them). For each small sphere, at least one filament connected to it must degenerate; otherwise, the structure is unstable and will continue to mutate. The figure below shows a stable mutation:

Now, we want to know, for a cell with a given code, how many stable structures exist in total. Two structures are considered identical if and only if they have the same number of small spheres, the same mass for each small sphere from head to tail, and the same connection method between each pair of adjacent small spheres from head to tail (either connected by a filament or directly connected by tangency). You only need to output the result modulo $1000000007$.

Input

The first line contains a positive integer $n$, representing the length of the cell's code. The second line contains $n$ digits, representing the given cell code, with no spaces in between.

Output

Contains only one integer, which is the number of cell structures modulo $1000000007$.

Examples

Input 1

1
1

Output 1

0

Input 2

1
5

Output 2

3

Input 3

2
11

Output 3

56

Constraints

For $5\%$ of the data, $n \leq 6$;

For $25\%$ of the data, $n \leq 25$;

For $60\%$ of the data, $n \leq 100$;

For $70\%$ of the data, $n \leq 300$;

For $100\%$ of the data, $n \leq 1\,000$.