K번째 이친수 찾기

0과 1로만 이루어진 수를 이진수라고 한다. 그중 다음 조건을 모두 만족하는 수를 이친수라고 한다.

1. 0으로 시작하지 않는다.
2. 1이 두 번 연속해서 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

대표적으로 1, 10, 100, 101, 1000, 1001은 이친수이다. 반대로 0010101은 첫 번째 조건을 만족하지 않고, 101101은 두 번째 조건을 만족하지 않으므로 이친수가 아니다.

모든 이친수를 이진수로 보았을 때의 값이 작은 순서대로 정렬하고, 앞에서부터 1번부터 번호를 붙인다. 자연수 K (1 ≤ K ≤ 1,000,000,000,000,000,000)가 주어질 때, K번째 이친수를 출력하는 프로그램을 작성하시오.

첫째 줄에 자연수 K가 주어진다.

첫째 줄에 K번째 이친수를 출력한다.