Stable Cell Structure

In the year 2222, scientists discovered an alien cell on a distant planet outside the galaxy. This strange cell is initially a rod‐shaped structure with a head, a tail, and a trunk. The cell contains a sequence of digits (its DNA) of length n, composed only of the digits 1–9 arranged along its trunk from head to tail.

The cell first undergoes a primary division: along its trunk the cell splits into k spherical parts. The trunk degrades into a filament that connects adjacent spheres. Due to uniform mass distribution, each spherical part has mass equal to the original mass divided by k. However, the DNA (the sequence of digits) is cut arbitrarily into k segments (each of length at least 1) in order from head to tail, so that the i-th sphere inherits a segment which, when interpreted as a decimal number, yields an integer value T_i.

Next, each sphere undergoes a secondary division: if a sphere contains a segment that represents the integer T, it is further subdivided into T small spheres arranged in a row. The mass of each small sphere is the mass of its parent sphere divided by T. After this stage the DNA vanishes.

Finally, the cell mutates. Initially, in each row the small spheres are connected by filament segments – the two end spheres have one connecting segment each, and every internal sphere has two. For the final structure to be stable, in each small sphere at least one of its adjacent filament connections must degrade (i.e. disappear), causing the connected spheres to become tangent. Two structures are considered identical if and only if:

• They consist of the same total number of small spheres.
• The mass of each small sphere (given by 1/(k × T_i) for the i-th group, repeated T_i times) is identical in order from head to tail.
• The connection status between every pair of adjacent small spheres is the same (either connected by an intact filament or by direct tangency after degradation).

Given the original DNA string, count the number of stable structures modulo 1000000007.

Note on Mutation: Suppose the final chain has M small spheres. Then there are M-1 connections. The rule is that the first connection (adjacent to the head) and the last connection (adjacent to the tail) must be degraded, and for every middle sphere (which has two adjacent connections) at least one of its two connections must degrade. If we denote a degraded connection by 1 and an intact connection by 0, then a valid pattern is a binary sequence of length M-1 with the first and last bits equal to 1 and no two consecutive 0’s in any pair of adjacent connections. It can be shown that if M ≥ 2 the number of valid connection patterns is equal to the Fibonacci number F(M-1) with F(1)=F(2)=1.

Process Summary:

1. Primary Division: Partition the DNA string (of length n) into k contiguous segments (1 ≤ k ≤ n). For each segmentation, interpret the i-th segment as an integer T_i (without leading zeros since digits are from 1 to 9).
2. Secondary Division: Each segment produces T_i small spheres. The total number of small spheres is M = T₁ + T₂ + ... + T_k.
3. Mutation: If M ≥ 2, there are exactly F(M-1) valid ways to degrade the connections, where F(1)=F(2)=1 and F(n)=F(n-1)+F(n-2) for n ≥ 3. If M < 2 the structure is unstable.

Your task is to sum over all possible primary divisions of the DNA string the number of stable structures (as computed from the mutation step) and output the result modulo 1000000007.

inputFormat

The input consists of a single line containing a non-empty string of digits (each from '1' to '9') representing the cell's DNA.

outputFormat

Output a single integer which is the total number of stable structures modulo 1000000007.

sample

1

0