Distinct Rounding Sequences

In his spare time, Ysuerpman likes to use his calculator to pass the time. He enters a long decimal number \(S\) which has \(n\) digits. Let the digit in the \(i\)th position from the least significant (i.e. \(S_1\) is the units digit, \(S_2\) the tens digit, etc.) be \(S_i\>.

In each operation, he selects a nonzero digit (i.e. a position \(i\) such that the current digit is nonzero) to "round off" with the following rule:

• If \(S_i<5\), then update \(S\) by subtracting \(S_i\cdot10^{i-1}\); that is, clear that digit without a carry.
• If \(S_i\ge5\), then update \(S\) by adding \(10^i\) and subtracting \(S_i\cdot10^{i-1}\) (i.e. round up); note that this effectively clears the \(i\)th digit and adds a carry of 1 to the \((i+1)\)th digit.

After a certain number of operations, \(S\) will eventually become \(0\). Two schemes are considered different if at some step a different digit position is chosen. Given the initial number \(S\) (possibly with leading zeroes when viewed from the least‐significant end), determine how many different sequences of operations will turn \(S\) to 0.

Observation: A careful analysis shows that regardless of the order in which the operations are performed, every nonzero digit of the original number will eventually be "rounded off" exactly once. (Even if additional operations are forced by a carry in the rounding‐up procedure, these extra operations are uniquely determined by the order in which the mandatory operations (those acting on digits originally nonzero) are performed.) Hence the number of different schemes is exactly the number of different orders in which the mandatory operations can be performed, which is \(k!\) where \(k\) is the count of nonzero digits in \(S\). Note that if \(S=0\) then we define the answer to be 1 (as no operation is performed).

inputFormat

The input consists of a single line containing the decimal number \(S\). \(S\) may have leading digits and its length \(n\) is at most moderate so that the answer (i.e. \(k!\)) fits in your language's built‐in big integer support. (Note that \(S\) is given in its usual representation, with the most significant digit first.)

outputFormat

Output a single integer denoting the number of different sequences of operations that will turn \(S\) to 0.

Hint: If \(S\) is not zero, let \(k\) be the number of digits in \(S\) that are nonzero. The answer is \(k!\). (For \(S=0\), output 1.)

sample

45

2