Base Numbers

Any non-negative integer can be written as a sequence of digits. The most common system is decimal, which uses ten digits (base 10). Other bases can also be used; for example, the binary system (base 2) is common in computing.

In general, a non-negative integer $n$ written as a sequence of digits

$$d_k,d_{k-1},\cdots,d_1,d_0$$

in the base-$r$ system (with $r > 1$) has the value

$$n = d_k \cdot r^{k} + d_{k-1} \cdot r^{k-1} + \cdots + d_1 \cdot r + d_0.$$

Every digit must be smaller than the base: $0 \le d_i < r$ for all $i$ with $0 \le i \le k$.

Bases greater than 10 are awkward because we need symbols for "digits" above 9. Letters are the usual fix, but the alphabet is still limited, so very large bases cannot be written this way.

Another approach writes each digit as a decimal number in its own right. For example, the hexadecimal number 1A8D can be written as (1-10-8-13)16. The base value is always appended (even in decimal) to avoid ambiguity. This text calls this format decimal-encoded notation.

A decimal-encoded number is valid only if it contains no unnecessary zeros: no extra leading zero may appear in the base or in any digit (the leading digit of a multi-digit number may not be 0, no digit's own decimal representation may have a leading zero, and the base may not have a leading zero), and every digit must be smaller than the base. For example, (1-0-0-0)7, (4-7689)7690, and (0)16 are valid, while (0-3-6)8, (1-02-3)6, (3-2-1)07, and (9)6 are invalid.

A collection of such valid decimal-encoded numbers was stored in a file, but a bug corrupted it: every decimal digit was preserved in its original order, yet all dashes and parentheses were lost. Each number therefore became a string of decimal digits only, and such strings are highly ambiguous — most can be read as many different numbers. For instance, 1234 could stand for (1-2-3)4, (12)34, (1-2)34, or (1)234.

For each corrupted string, determine how many different decimal-encoded numbers could have produced it. Two decimal-encoded numbers are counted as different even if they have the same value.

The input consists of several lines. Each line contains one code — a string of decimal digits whose length is between 1 and 35, inclusive. The input ends with a line containing a single hash character #.

For each code, print one line. If no valid decimal-encoded number yields the code, print The code CCC is invalid.. Otherwise print The code CCC can represent X numbers., where CCC is the code itself and X is the number of distinct decimal-encoded numbers that reduce to the code once dashes and parentheses are removed. Representations are counted as different even when they have the same value.