Binary Suffix Numbers

A positive number \(A\) is called a binary suffix number if it satisfies the following two conditions:

• The decimal representation of \(A\) contains only the digits 0 and 1 (and does not have any leading zero, so its first digit is always 1).
• Let \(B\) be the binary representation of \(A\) (without the prefix 0b). Then the string representation of \(A\) is a suffix of \(B\). In other words, if \(k\) is the number of digits in \(A\), then the last \(k\) bits of \(B\) exactly match the digits of \(A\).

For example, consider \(A = 10\): its decimal representation is "10" and its binary representation is "1010". Since "1010" ends with "10", \(A = 10\) is a valid binary suffix number.

Your task is: Given a positive integer \(N\), find the \(N\)th binary suffix number in increasing order. The ordering is based on the numerical value of \(A\).

Note: For a number \(A\) with \(k\) digits, the condition can be equivalently written in mathematical terms as:

[ A \bmod 2^k = \text{binary}(A), ]

where \(\text{binary}(A)\) stands for interpreting the string of \(A\) as a binary number.

inputFormat

The input consists of a single line containing a positive integer \(N\) (\(1 \le N\)).

Example:

5

outputFormat

Output the \(N\)th binary suffix number.

Example:

101

sample

1

1