Find the K-th Non-Adjacent Bit Number

Given a non-negative integer \( k \), the task is to find the \( k \)-th non-negative number in a sequence where each number's binary representation does not have two adjacent \( 1 \) bits. The binary representation is considered without the leading zeros. For example, the binary representation of 5 is 101 which is valid, but 3 is represented as 11 which is invalid since it contains adjacent ones.

Input Constraints: \( k \) is a non-negative integer. The sequence is 0-indexed.

Note: The result should be obtained by testing each number in increasing order and checking the condition that no two consecutive bits in its binary representation are set.

The solution is expected to efficiently compute the answer for moderate values of \( k \). The condition for a valid number can be formulated in \( \LaTeX \) as: \( \text{if } n \text{ is a number, it is valid if } \binom{n}{ \text{binary} } \text{ does not contain } 11 \).

inputFormat

A single integer ( k ) is provided via standard input (stdin). This integer represents the 0-indexed position in the sequence.

outputFormat

Output a single integer to standard output (stdout), which is the ( k )-th non-negative number whose binary representation does not contain adjacent 1s.## sample

4

5