Problem Description

In the year 2222, humans discovered life on a planet outside the Milky Way and brought back a cell to Earth. After extensive research, humans have fully understood the development patterns of these cells:

The initial form of these cells is "cylindrical," with one end being the head, the other end being the tail, and the middle being the body. The cell contains a sequence of codes (which you can think of as the cell's DNA). The code is a numeric string of length n, containing only the digits 1 through 9, arranged along the body of the cell from head to tail.

First, the cell undergoes a primary division. The cell will divide along the body into several spheres, with the body degenerating into filamentous connections between adjacent spheres. During this division, the mass is evenly distributed. In other words, if it divides into k spheres, each sphere will have 1/k of the original mass. However, the distribution of the code is uncertain. If divided into k spheres, the code will be 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 following figure shows one valid primary division:

Next, the cell undergoes a secondary division. Each sphere contains a small segment of the code (note that it is ordered), which we consider as a decimal number T. This sphere will be divided into T smaller spheres, arranged in a row, connected by the filamentous connections from the body, and the mass remains evenly distributed, with each smaller sphere having 1/T of the original sphere's mass. At this point, the code has served its purpose and disappears. The following figure shows a secondary division:

Finally, the cell undergoes mutation. The filamentous connections between adjacent smaller spheres may degenerate, causing these two smaller spheres to connect directly in contact. Clearly, after the secondary division, each smaller sphere, except for the two ends, has two filamentous connections (the head and tail spheres have only one connection each). For each smaller sphere, at least one of the connecting filamentous connections must degenerate, otherwise, the structure is unstable and will continue to mutate. The following figure shows a stable mutation:

Now, we want to know how many stable structures are possible for a cell with a given code. Two structures are considered identical if and only if they have the same number of smaller spheres, the same mass for each smaller sphere from head to tail, and the same connection method between each pair of adjacent smaller spheres (either connected by filamentous connections or directly in contact). You only need to answer this result modulo 1000000007.

Input Format

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

The second line contains n digits, representing the given cell's code, with no spaces in between.

Output Format

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

Sample Input and Output

Sample Input #1

1
1

Sample Output #1

0

Sample Input #2

1
5

Sample Output #2

3

Sample Input #3

2
11

Sample Output #3

56

Notes

For 5% of the data, n ≤ 6;

For 25% of the data, n ≤ 25;

For 60% of the data, n ≤ 100;

For 70% of the data, n ≤ 300;

For 100% of the data, n ≤ 1,000.

见题面 Input 部分

见题面 Output 部分