Problem G
Organ-free Man

Every so often, a shipment of universal robots comes from Earth to Mars in order to help you with routine colonization tasks. The robots are called Organ-free Men (precisely OFMv5001.41.912) and each one of them is identified by a unique serial number, which is a positive integer.

To prevent space theft, OFMs are transported from Earth to Mars in a locked state and have to be first unlocked by a special password. The password to unlock an OFM is based on its serial number and a function $f(x)$. The function $f(x)$ is defined as follows.

If $0 \le x \le 9$, then $f(x) = x!$, and if $x > 9$, then $f(x) = (x \mod 10)! + f(\lfloor x/10 \rfloor $). The brackets $\lfloor \rfloor $ denote the floor value of a number (e.g. $\lfloor 2.43 \rfloor = 2$). Exclamation mark denotes the factorial, i.e., $x! = 1 \cdot 2 \cdot \cdots \cdot x$ for $x > 0$ and $0! = 1$.

To unlock an OFM with a serial number $y$, you need to input smallest such non-negative integer $x$, so that $f(x) = y$ holds.

Will you manage to unlock all robots that were shipped to you?


The input consists of one integer $y$ ($1 \le y \le 10^9$), the serial number of a particular OFM.


Output a single non-negative integer $x$, the password to unlock the particular OFM.

Sample Input 1 Sample Output 1
Sample Input 2 Sample Output 2

Please log in to submit a solution to this problem

Log in