AT_abc451_d [ABC451D] Concat Power of 2

We call a positive integer a **good integer** if it satisfies the following condition. - Condition: It can be obtained by choosing one or more powers of $ 2 $ ( $ 1, 2, 4, 8, 16, \dots $ ) (repetition and reordering allowed), concatenating them as strings, and interpreting the result as an integer. Find the $ N $ -th smallest good integer. It is guaranteed that the $ N $ -th smallest good integer is at most $ 10^9 $ .

The input is given from Standard Input in the following format: > $ N $

Output the answer.

### Sample Explanation 1 Listing good integers in ascending order gives $ 1, 2, 4, 8, 11, 12, 14, 16, 18, 21, \dots $ . ### Constraints - $ N $ is a positive integer. - The $ N $ -th smallest good integer is at most $ 10^9 $ .