시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 523 241 188 48.831%

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 들 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

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

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 (1), (2)번 규칙에 위배되므로 이친수가 아니다.

이와 같은 이친수를 이진수의 크기 순서대로 정렬하여 차례로 번호를 붙인다. 이를테면 첫 번째 이친수는 1, 두 번째 이친수는 10, 네 번째 이친수는 101이 되는 식이다.

자연수 K(1≤K≤1,000,000,000,000,000,000)가 주어졌을 때, K번째 이친수를 찾아내는 프로그램을 작성하시오.

입력

첫째 줄에 K가 주어진다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1

7

예제 출력 1

1010
W3sicHJvYmxlbV9pZCI6IjIyMDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzRcdWNlNWNcdWMyMTggXHVjYzNlXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD4wXHVhY2ZjIDFcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzIxOFx1Yjk3YyBcdWM3NzRcdWM5YzRcdWMyMThcdWI3N2MgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjNzc0XHVjOWM0XHVjMjE4IFx1YjRlNCBcdWQyYjlcdWJjYzRcdWQ1NWMgXHVjMTMxXHVjOWM4XHVjNzQ0IFx1YWMxNlx1YjI5NCBcdWFjODNcdWI0ZTRcdWM3NzQgXHVjNzg4XHViMjk0XHViMzcwLCBcdWM3NzRcdWI0ZTRcdWM3NDQgXHVjNzc0XHVjZTVjXHVjMjE4KHBpbmFyeSBudW1iZXIpXHViNzdjIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHVjZTVjXHVjMjE4XHViMjk0IFx1YjJlNFx1Yzc0Y1x1Yzc1OCBcdWMxMzFcdWM5YzhcdWM3NDQgXHViOWNjXHVjODcxXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1Yzc3NFx1Y2U1Y1x1YzIxOFx1YjI5NCAwXHVjNzNjXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1Yzc3NFx1Y2U1Y1x1YzIxOFx1YzVkMFx1YzExY1x1YjI5NCAxXHVjNzc0IFx1YjQ1MCBcdWJjODggXHVjNWYwXHVjMThkXHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjA5OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1Yzk4OSwgMTFcdWM3NDQgXHViZDgwXHViZDg0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yjg1YyBcdWFjMTZcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQgMSwgMTAsIDEwMCwgMTAxLCAxMDAwLCAxMDAxIFx1YjRmMVx1Yzc3NCBcdWM3NzRcdWNlNWNcdWMyMThcdWFjMDAgXHViNDFjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgMDAxMDEwMVx1Yzc3NFx1YjA5OCAxMDExMDFcdWM3NDAgXHVhYzAxXHVhYzAxICgxKSwgKDIpXHViYzg4IFx1YWRkY1x1Y2U1OVx1YzVkMCBcdWM3MDRcdWJjMzBcdWI0MThcdWJiYzBcdWI4NWMgXHVjNzc0XHVjZTVjXHVjMjE4XHVhYzAwIFx1YzU0NFx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWM3NzRcdWNlNWNcdWMyMThcdWI5N2MgXHVjNzc0XHVjOWM0XHVjMjE4XHVjNzU4IFx1ZDA2Y1x1YWUzMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjODE1XHViODJjXHVkNTU4XHVjNWVjIFx1Y2MyOFx1Yjg0MFx1Yjg1YyBcdWJjODhcdWQ2MzhcdWI5N2MgXHViZDk5XHVjNzc4XHViMmU0LiBcdWM3NzRcdWI5N2NcdWQxNGNcdWJhNzQgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM3NzRcdWNlNWNcdWMyMThcdWIyOTQgMSwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM3NzRcdWNlNWNcdWMyMThcdWIyOTQgMTAsIFx1YjEyNCBcdWJjODhcdWM5ZjggXHVjNzc0XHVjZTVjXHVjMjE4XHViMjk0IDEwMVx1Yzc3NCBcdWI0MThcdWIyOTQgXHVjMmRkXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3OTBcdWM1ZjBcdWMyMTggSygxJmxlO0smbGU7MSwwMDAsMDAwLDAwMCwwMDAsMDAwLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgS1x1YmM4OFx1YzlmOCBcdWM3NzRcdWNlNWNcdWMyMThcdWI5N2MgXHVjYzNlXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMmY1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMjAxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUGluYXJ5IiwiZGVzY3JpcHRpb24iOiI8cD4mbGRxdW87UGluYXJ5JnJkcXVvOyBudW1iZXIgaXMgYSBwb3NpdGl2ZSBudW1iZXIgdXNpbmcgb25seSB0d28gZGlnaXRzICZsZHF1bzswJnJkcXVvOyBhbmQgJmxkcXVvOzEmcmRxdW87IHdpdGggdXN1YWwgcnVsZSB0aGF0IGl0IG11c3Qgbm90IGJlZ2luIHdpdGggYSAwLCBhbmQgdGhlIGFkZGl0aW9uYWwgcnVsZSB0aGF0IHR3byBzdWNjZXNzaXZlIGRpZ2l0cyBtdXN0IG5vdCBiZSBib3RoICZsZHF1bzsxJnJkcXVvOy4gVGhpcyBtZWFucyB0aGF0IHRoZSBmYWN0b3IgJmxkcXVvOzExJnJkcXVvOyBpcyBmb3JiaWRkZW4gaW4gdGhlIHN0cmluZy4gU28gdGhlIGFsbG93ZWQgUGluYXJ5IHdyaXRpbmdzIGFyZSAxLCAxMCwgMTAwLCAxMDEsIDEwMDAsIDEwMDEsICZoZWxsaXA7LCAxMDAwMTAxMDEwMTAxMDAwMTAwMDEuIEZvciBleGFtcGxlLCAmbGRxdW87MTAwMTAxMDAwJnJkcXVvOyBpcyBhIFBpbmFyeSBudW1iZXIsIGJ1dCBuZWl0aGVyICZsZHF1bzswMDEwMTAxJnJkcXVvOyBub3IgJmxkcXVvOzEwMTEwMDAxJnJkcXVvOyBhcmUgUGluYXJ5IG51bWJlcnMuPFwvcD5cclxuXHJcbjxwPkVhY2ggUGluYXJ5IG51bWJlciByZXByZXNlbnRzIGEgcG9zaXRpdmUgaW50ZWdlciBpbiB0aGUgb3JkZXIgdGhleSBhcHBlYXIgKHVzaW5nIGxlbmd0aCBvcmRlciwgbGV4aWNvZ3JhcGhpYyBvcmRlciksIHRoYXQgaXMsIDEgaXMgbWFwcGVkIHRvIDEsIDEwIGlzIG1hcHBlZCB0byAyLiBBbmQgMTAwLCAxMDEgYW5kIDEwMDAgYXJlIG1hcHBlZCB0byAzLCA0IGFuZCA1LCByZXNwZWN0aXZlbHkuIFlvdSBhcmUgdG8gd3JpdGUgYSBwcm9ncmFtIHRvIGdlbmVyYXRlIFBpbmFyeSBudW1iZXIgcmVwcmVzZW50YXRpb25zIGZvciBpbnRlZ2VycyBnaXZlbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgYSBwb3N0aXZlIGludGVnZXIgMSZuYnNwOyZsZTsgSyAmbGU7IDEsMDAwLDAwMCwwMDAsMDAwLDAwMCwwMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHdyaXRlIHRvIHN0YW5kYXJkIG91dHB1dC4gUHJpbnQgZXhhY3RseSBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNhc2UuIEZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgdGhlIFBpbmFyeSBudW1iZXIgcmVwcmVzZW50YXRpb24gZm9yIGlucHV0IGludGVnZXIuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d