Problem E
Heather Code

January 26, 2020. Photo by osseous

Heather Grey has decided she would like to unlock the combination lock that USC has used to lock up Tommy Trojan before the UCLA versus USC football game.

The multi-ring combination lock has $7$ rings on it. Each ring has the 10 digits $0,1,2,\dots 9$ printed on it in that order. One row of the lock represents the code. Initially, the code entered is $0000000$. Heather wants to crack the lock, so she needs to try every possible digit combination. The rings must be turned one digit at a time and can only be turned in one direction, so that it takes one turn to get from $0$ to $1$, one turn to get from $1$ to $2$, and so on, and one turn to get from $9$ to $0$. Heather wants to take the least number of turns possible, so she uses the following procedure: every second, she chooses a ring and moves it by one turn, such that she always chooses the rightmost ring that will not cause her to try a code she’s already tried. (If it’s impossible for her to choose such a ring, she stops.)

Here is a table of the codes Heather tries for $n$ turns, with $0 \leq n \leq 20$:

$\begin{array}{l|l} 0 & 0000000\\ 1 & 0000001\\ 2 & 0000002\\ 3 & 0000003\\ 4 & 0000004\\ 5 & 0000005\\ 6 & 0000006\\ 7 & 0000007\\ 8 & 0000008\\ 9 & 0000009\\ 10 & 0000019\\ 11 & 0000010\\ 12 & 0000011\\ 13 & 0000012\\ 14 & 0000013\\ 15 & 0000014\\ 16 & 0000015\\ 17 & 0000016\\ 18 & 0000017\\ 19 & 0000018\\ 20 & 0000028 \end{array}$

Input

The only line of the input contains the integer ($1 \leq n \leq 9\, 999\, 999$).

Output

Print $7$ digits representing the code that Heather tries on her $n$th turn. It is guaranteed that Heather will make at least $n$ turns.

1

0000001

10

0000019

20

0000028

100

0000190

9999999

9000000