시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 64 24 10 47.619%

문제

피보나치 진법이란 0과 1만을 이용해 자연수를 유일하게 표현하는 방법이다.

자연수 \(N\)을 피보나치 진법 \(N=\overline { a_{n}a_{n-1}\cdots a_{1} } _{F} \) 으로 나타냈을 때, \(N\)의 값은 \(N=a_{ n }\cdot F_{ n }+a_{ n-1 }\cdot F_{ n-1}+ \cdots + a_1 \cdot F_1\)이 된다. \(F_k\)는 피보나치 수열로 \(F_0 = F_1 = 1, F_i = F_{i-1} + F_{i-2}\)이다. 각 자연수를 유일하게 표현하기 위해서 피보나치 진법에서는 1이 인접할 수 없다.

다음은 자연수 일부를 피보나치 진법으로 나타낸 것이다.

\[ 1 = 1_F \\ 2 = 10_F \\ 3 = 100_F \\ 4 = 101_F \\ 5 = 1000_F \\ 6 = 1001_F \\ 7 = 1010_F \]

상근이는 자연수를 피보나치 진법으로 순서대로 나타낸 뒤, 그 수를 모두 붙였다. 즉, 이 문열의 첫 부분은 110100101100010011010... 이 된다.

상근이는 이 문자열의 처음 N글자 중에 1의 개수가 몇 개나 있는지 궁금해졌다.

N이 주어졌을 때, 상근이가 만든 문자의 처음 N글자 중 1의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 1015)

출력

첫째 줄에 상근이의 문자열의 처음 N글자 중 1의 개수를 출력한다.

예제 입력 1

21

예제 출력 1

10
W3sicHJvYmxlbV9pZCI6IjM1NjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjOWM0XHViYzk1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjOWM0XHViYzk1XHVjNzc0XHViNzgwIDBcdWFjZmMgMVx1YjljY1x1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzQgXHVjNzkwXHVjNWYwXHVjMjE4XHViOTdjIFx1YzcyMFx1Yzc3Y1x1ZDU1OFx1YWM4YyBcdWQ0NWNcdWQ2MDRcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3OTBcdWM1ZjBcdWMyMTggXFwoTlxcKVx1Yzc0NCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjOWM0XHViYzk1IFxcKE49XFxvdmVybGluZSB7IGFfe259YV97bi0xfVxcY2RvdHMgYV97MX0gfSBfe0Z9IFxcKSBcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGM4XHVjNzQ0IFx1YjU0YywgXFwoTlxcKVx1Yzc1OCBcdWFjMTJcdWM3NDAgXFwoTj1hX3sgbiB9XFxjZG90IEZfeyBuIH0rYV97IG4tMSB9XFxjZG90IEZfeyBuLTF9KyBcXGNkb3RzICsgYV8xIFxcY2RvdCBGXzFcXClcdWM3NzQgXHViNDFjXHViMmU0LiBcXChGX2tcXClcdWIyOTQgXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1YzVmNFx1Yjg1YyBcXChGXzAgPSBGXzEgPSAxLCBGX2kgPSBGX3tpLTF9ICsgRl97aS0yfVxcKVx1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yjk3YyBcdWM3MjBcdWM3N2NcdWQ1NThcdWFjOGMgXHVkNDVjXHVkNjA0XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjOWM0XHViYzk1XHVjNWQwXHVjMTFjXHViMjk0IDFcdWM3NzQgXHVjNzc4XHVjODExXHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0Y1x1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMTggXHVjNzdjXHViZDgwXHViOTdjIFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWM5YzRcdWJjOTVcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI4IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XFxbIDEgPSAxX0YgXFxcXCAyID0gMTBfRiBcXFxcIDMgPSAxMDBfRiBcXFxcIDQgPSAxMDFfRiBcXFxcIDUgPSAxMDAwX0YgXFxcXCA2ID0gMTAwMV9GIFxcXFwgNyA9IDEwMTBfRiBcXF08XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yjk3YyBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjOWM0XHViYzk1XHVjNzNjXHViODVjIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjggXHViNGE0LCBcdWFkZjggXHVjMjE4XHViOTdjIFx1YmFhOFx1YjQ1MCBcdWJkOTlcdWM2MDBcdWIyZTQuIFx1Yzk4OSwgXHVjNzc0IFx1YmIzOFx1YzVmNFx1Yzc1OCBcdWNjYWIgXHViZDgwXHViZDg0XHVjNzQwIDExMDEwMDEwMTEwMDAxMDAxMTAxMC4uLiBcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzc0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWNjOThcdWM3NGMgTlx1YWUwMFx1Yzc5MCBcdWM5MTFcdWM1ZDAgMVx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHViYTg3IFx1YWMxY1x1YjA5OCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDgxXHVhZTA4XHVkNTc0XHVjODRjXHViMmU0LjxcL3A+XHJcblxyXG48cD5OXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWI5Y2NcdWI0ZTAgXHViYjM4XHVjNzkwXHVjNzU4IFx1Y2M5OFx1Yzc0YyBOXHVhZTAwXHVjNzkwIFx1YzkxMSAxXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgTiAmbGU7IDEwPHN1cD4xNTxcL3N1cD4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1Y2M5OFx1Yzc0YyBOXHVhZTAwXHVjNzkwIFx1YzkxMSAxXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzU2NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZpYm9uYWNjaSBTeXN0ZW0iLCJkZXNjcmlwdGlvbiI6IjxwPkxpdHRsZSBKb2huIHN0dWRpZXMgbnVtZXJhbCBzeXN0ZW1zLiBBZnRlciBsZWFybmluZyBhbGwgYWJvdXQgZml4ZWQtYmFzZSBzeXN0ZW1zLCBoZSBiZWNhbWUgaW50ZXJlc3RlZCBpbiBtb3JlIHVudXN1YWwgY2FzZXMuIEFtb25nIHRob3NlIGNhc2VzIGhlIGZvdW5kIGEgRmlib25hY2NpIHN5c3RlbSwgd2hpY2ggcmVwcmVzZW50cyBhbGwgbmF0dXJhbCBudW1iZXJzIGluIGFuIHVuaXF1ZSB3YXkgdXNpbmcgb25seSB0d28gZGlnaXRzOiB6ZXJvIGFuZCBvbmUuIEJ1dCB1bmxpa2UgdXN1YWwgYmluYXJ5IHNjYWxlIG9mIG5vdGF0aW9uLCBpbiB0aGUgRmlib25hY2NpIHN5c3RlbSB5b3UgYXJlIG5vdCBhbGxvd2VkIHRvIHBsYWNlIHR3byAxcyBpbiBhZGphY2VudCBwb3NpdGlvbnMuPFwvcD5cclxuXHJcbjxwPk9uZSBjYW4gcHJvdmUgdGhhdCBpZiB5b3UgaGF2ZSBudW1iZXIgXFwoTj1cXG92ZXJsaW5lIHsgYV97bn1hX3tuLTF9XFxjZG90cyBhX3sxfSB9IF97Rn0gXFwpIGluIEZpYm9uYWNjaSBzeXN0ZW0sIGl0cyB2YWx1ZSBpcyBlcXVhbCB0byBcXChOPWFfeyBuIH1cXGNkb3QgRl97IG4gfSthX3sgbi0xIH1cXGNkb3QgRl97IG4tMX0rIFxcY2RvdHMgKyBhXzEgXFxjZG90IEZfMVxcKSwgd2hlcmUgXFwoRl9rXFwpIGlzIGEgdXN1YWwgRmlib25hY2NpIHNlcXVlbmNlIGRlZmluZWQgYnkgXFwoRl8wID0gRl8xID0gMSwgRl9pID0gRl97aS0xfSArIEZfe2ktMn1cXCkuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBmaXJzdCBmZXcgbmF0dXJhbCBudW1iZXJzIGhhdmUgdGhlIGZvbGxvd2luZyB1bmlxdWUgcmVwcmVzZW50YXRpb25zIGluIEZpYm9uYWNjaSBzeXN0ZW06PFwvcD5cclxuXHJcbjxwPlxcWyAxID0gMV9GIFxcXFwgMiA9IDEwX0YgXFxcXCAzID0gMTAwX0YgXFxcXCA0ID0gMTAxX0YgXFxcXCA1ID0gMTAwMF9GIFxcXFwgNiA9IDEwMDFfRiBcXFxcIDcgPSAxMDEwX0YgXFxdPFwvcD5cclxuXHJcbjxwPkpvaG4gd3JvdGUgYSB2ZXJ5IGxvbmcgc3RyaW5nIChjb25zaWRlciBpdCBpbmZpbml0ZSkgY29uc2lzdGluZyBvZiBjb25zZWN1dGl2ZSByZXByZXNlbnRhdGlvbnMgb2YgbmF0dXJhbCBudW1iZXJzIGluIEZpYm9uYWNjaSBzeXN0ZW0uIEZvciBleGFtcGxlLCB0aGUgZmlyc3QgZmV3IGRpZ2l0cyBvZiB0aGlzIHN0cmluZyBhcmUgMTEwMTAwMTAxMTAwMDEwMDExMDEwLi4uPFwvcD5cclxuXHJcbjxwPkhlIGlzIHZlcnkgaW50ZXJlc3RlZCwgaG93IG1hbnkgdGltZXMgdGhlIGRpZ2l0IDEgb2NjdXJzIGluIHRoZSBOLXRoIHByZWZpeCBvZiB0aGUgc3RyaW5nLiBSZW1lbWJlciB0aGF0IHRoZSBOLXRoIHByZWZpeCBvZiB0aGUgc3RyaW5nIGlzIGp1c3QgYSBzdHJpbmcgY29uc2lzdGluZyBvZiBpdHMgZmlyc3QgTiBjaGFyYWN0ZXJzLjxcL3A+XHJcblxyXG48cD5XaXJ0ZSBhIHByb2dyYW0gd2hpY2ggZGV0ZXJtaW5lcyBob3cgbWFueSB0aW1lcyB0aGUgZGlnaXQgMSBvY2N1cnMgaW4gTi10aCBwcmVmaXggb2YgSm9obiYjMzk7cyBzdHJpbmcuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBOICgwICZsZTsgTiAmbmJzcDsmbGU7IDEwPHN1cD4xNTxcL3N1cD4pLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyIC0gdGhlIG51bWJlciBvZiAxcyBpbiBOLXRoIHByZWZpeCBvZiBKb2huJiMzOTtzIHN0cmluZy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=