Find the K-th Pinary Number

A binary number is a number written using only 0 and 1. Among them, a pinary number is a number that satisfies both conditions below.

1. It does not start with 0.
2. It never contains two consecutive 1s. In other words, it does not contain 11 as a substring.

For instance, 1, 10, 100, 101, 1000, and 1001 are pinary numbers. On the other hand, 0010101 violates the first condition, and 101101 violates the second condition, so they are not pinary numbers.

Sort all pinary numbers by their value as binary numbers in increasing order, then number them starting from 1. Given a natural number K (1 ≤ K ≤ 1,000,000,000,000,000,000), write a program that outputs the K-th pinary number.

The first line contains the natural number K.

Print the K-th pinary number on the first line.