Description

In the year 2222, humans discovered life on a planet outside the Milky Way and brought back a cell to Earth. After repeated research, humans have fully understood how this type of cell develops:

The cell initially has a “long strip” shape, with a head at one end and a tail at the other, and a trunk in the middle. Inside the cell there is a sequence of codes (you may think of it as the cell’s DNA). The code is a digit string of length $n$, containing only the 9 digits $1 \sim 9$, arranged along the trunk from head to tail.

First, the cell undergoes a split. The cell splits along the trunk into several spheres, and the trunk degenerates into filaments that connect adjacent spheres. During the split, mass is evenly distributed. In other words, if it splits into $k$ spheres, each sphere has mass $1/k$ of the original. However, the distribution of the code is uncertain. If it is split into $k$ spheres, the code is cut into $k$ segments (each segment has length at least 1), and these segments are placed into the spheres in order from head to tail. The following figure shows one valid split:

Next, the cell undergoes a second split. For each sphere, it contains a short segment of the code (note that it is ordered). Treat this segment as a decimal number $T$. This sphere is then divided into $T$ small spheres, arranged in a line, connected by filaments formed from the degenerated trunk, and the mass is still evenly distributed, so each small sphere has mass $1/T$ of the original sphere. At this point, the code has served its purpose and disappears. The following figure shows the second split:

Finally, the cell mutates. The filament between two adjacent small spheres may degenerate, and then the two small spheres are directly connected in a tangent way. Clearly, after the second split, each small sphere except the two ends has two filaments connected to it (the small spheres at the head and tail ends have only one filament). For each small sphere, at least one filament connected to it must degenerate; otherwise, the structure is unstable and will continue to mutate. The following figure shows one stable mutation:

Now we want to know: for a cell with a given code, how many different stable structures are there in total. Two structures are considered the same if and only if they have the same number of small spheres, from head to tail each small sphere has the same mass, and from head to tail the connection between every pair of adjacent small spheres is the same (either both connected by a filament, or both directly connected tangentially). You only need to output the answer modulo 1000000007.

Input Format

The first line contains a positive integer $n$, indicating the length of the cell code.

The second line contains $n$ digits, which form the given cell code, with no spaces.

Output Format

Output only one integer, the number of possible structures modulo 1000000007.

1
1

0

1
5

3

2
11

56

Hint

For 5% of the testdata, $n \le 6$.

For 25% of the testdata, $n \le 25$.

For 60% of the testdata, $n \le 100$.

For 70% of the testdata, $n \le 300$.

For 100% of the testdata, $n \le 1\,000$.

Translated by ChatGPT 5