Counting Base Representations

A string S consisting only of decimal digits is given. Count how many ways parentheses and spaces can be restored so that the string becomes a valid base representation.

A representation is defined as follows.

• A nonempty suffix of the string is used as the base b. The base must be an integer at least 2 and must not have unnecessary leading zeros.
• The preceding nonempty prefix is split into one or more digit values. Each digit value is written in decimal and must satisfy 0 <= d < b.
• A digit value must not have unnecessary leading zeros. The value zero may be written only as the single string 0.

Even if two representations denote the same numeric value, they are counted separately when their split positions are different.

The first line contains a string S consisting only of decimal digits. The length of S is at most 35.

Print the number of possible representations.