시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2497 1087 820 46.354%

문제

세계적인 이진수 매니아 현수는 오늘도 이진수를 연구하고 있다.

오늘은 이진수로 나타냈을 때, k자리 이하인 모든 자연수의 합을 구해보려고 한다.

k가 주어졌을 때, 이진수로 나타냈을 때, k자리 이하인 모든 자연수의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 k가 주어진다. (1 ≤ k ≤ 106)

출력

첫째 줄에 이진수로 나타냈을 때, k자리 이하인 모든 자연수의 합을 이진수로 출력한다.

예제 입력 1

3

예제 출력 1

11100

힌트

1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 = 111002

W3sicHJvYmxlbV9pZCI6Ijg3NDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzRcdWM5YzRcdWMyMTggXHVkNTY5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMzhcdWFjYzRcdWM4MDFcdWM3NzggXHVjNzc0XHVjOWM0XHVjMjE4IFx1YjllNFx1YjJjOFx1YzU0NCBcdWQ2MDRcdWMyMThcdWIyOTQgXHVjNjI0XHViMjk4XHViM2M0IFx1Yzc3NFx1YzljNFx1YzIxOFx1Yjk3YyBcdWM1ZjBcdWFkNmNcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MjRcdWIyOThcdWM3NDAgXHVjNzc0XHVjOWM0XHVjMjE4XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBjOFx1Yzc0NCBcdWI1NGMsIGtcdWM3OTBcdWI5YWMgXHVjNzc0XHVkNTU4XHVjNzc4IFx1YmFhOFx1YjRlMCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzQ0IFx1YWQ2Y1x1ZDU3NFx1YmNmNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPmtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0XHVjOWM0XHVjMjE4XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBjOFx1Yzc0NCBcdWI1NGMsIGtcdWM3OTBcdWI5YWMgXHVjNzc0XHVkNTU4XHVjNzc4IFx1YmFhOFx1YjRlMCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBrXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBrICZsZTsgMTA8c3VwPjY8XC9zdXA+KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCZuYnNwO1x1YzkwNFx1YzVkMCBcdWM3NzRcdWM5YzRcdWMyMThcdWI4NWMgXHViMDk4XHVkMGMwXHViMGM4XHVjNzQ0IFx1YjU0Yywga1x1Yzc5MFx1YjlhYyBcdWM3NzRcdWQ1NThcdWM3NzggXHViYWE4XHViNGUwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjNzc0XHVjOWM0XHVjMjE4XHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+MSArIDIgKyAzICsgNCArIDUgKyA2ICsgNyA9IDI4ID0gMTExMDA8c3ViPjI8XC9zdWI+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI4NzQxIiwicHJvYmxlbV9sYW5nIjoiMyIsInRpdGxlIjoiU3VtYSIsImRlc2NyaXB0aW9uIjoiPHA+T2Qga2llZHkgQWRpIHByemVzdGFcdTAxNDIgemFqbW93YVx1MDEwNyBzaVx1MDExOSBvZ3JvZG5pY3R3ZW0sIHRvIGNhXHUwMTQyeW1pIGRuaWFtaSBzaWVkemkgdyBzd29pbSBwb2tvanUgYW5hbGl6dWpcdTAxMDVjIHdcdTAxNDJhc25vXHUwMTViY2kgbGljemIgdyB6YXBpc2llIGJpbmFybnltLiBPZCB0ZWdvIGN6YXN1IG5cdTAxMTlrYSBnbyBuYXN0XHUwMTE5cHVqXHUwMTA1Y3kgcHJvYmxlbTogem5hbGV6aWVuaWUgc3VteSB3c3p5c3RraWNoIGRvZGF0bmljaCBsaWN6YiBjYVx1MDE0Mmtvd2l0eWNoLCBrdCZvYWN1dGU7cmUgdyB6YXBpc2llIGJpbmFybnltIG1halx1MDEwNSBjbyBuYWp3eVx1MDE3Y2VqIGsgY3lmci4gQWRpIG5pZSBtYSBwb215c1x1MDE0MnUsIGphayBzaVx1MDExOSBkbyB0ZWdvIHphYnJhXHUwMTA3LCB3aVx1MDExOWMgbyBwb21vYyBwb3Byb3NpXHUwMTQyIENpZWJpZS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5QaWVyd3N6eSB3aWVyc3ogd2VqXHUwMTViY2lhIHphd2llcmEgamVkblx1MDEwNSBsaWN6Ylx1MDExOSBjYVx1MDE0Mmtvd2l0XHUwMTA1IGsgKDEgJmxlOyBrICZsZTsgMTA8c3VwPjY8XC9zdXA+KS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QaWVyd3N6eSBpIGplZHlueSB3aWVyc3ogd3lqXHUwMTViY2lhIHBvd2luaWVuIHphd2llcmFcdTAxMDcgamVkblx1MDEwNSBsaWN6Ylx1MDExOSAtIHN1bVx1MDExOSBkb2RhdG5pY2ggbGljemIgY2FcdTAxNDJrb3dpdGN5aCwga3Qmb2FjdXRlO3JlIHcgemFwaXNpZSBiaW5hcm55bSBtYWpcdTAxMDUgY28gbmFqd3lcdTAxN2NlaiBrIGN5ZnIuIExpY3piXHUwMTE5IHRcdTAxMTkgbmFsZVx1MDE3Y3kgd3lwaXNhXHUwMTA3IHcgc3lzdGVtaWUgZHcmb2FjdXRlO2prb3d5bS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPjEgKyAyICsgMyArIDQgKyA1ICsgNiArIDcgPSAyOCA9IGJpbmFybmllJm5ic3A7MTExMDA8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDNmNFx1Yjc4MFx1YjRkY1x1YzViNCJ9XQ==