문제
어떤 자연수 N을 2의 멱수의 합으로 나타내는 경우의 수를 구하는 프로그램을 작성하시오. 2의 멱수라는 것은, 2^k으로 표현되는 자연수를 의미한다.
예를 들어 7을 2의 멱수의 합으로 나타내는 경우의 수는 다음의 여섯 가지가 있다.
- 1+1+1+1+1+1+1
- 1+1+1+1+1+2
- 1+1+1+2+2
- 1+1+1+4
- 1+2+2+2
- 1+2+4
출력
첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다.
W3sicHJvYmxlbV9pZCI6IjI0MTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiIyXHVjNzU4IFx1YmE3MVx1YzIxOFx1Yzc1OCBcdWQ1NjkiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzViNFx1YjVhNCBcdWM3OTBcdWM1ZjBcdWMyMTggTlx1Yzc0NCAyXHVjNzU4IFx1YmE3MVx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIDJcdWM3NTggXHViYTcxXHVjMjE4XHViNzdjXHViMjk0IFx1YWM4M1x1Yzc0MCwgMl5rXHVjNzNjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQxOFx1YjI5NCBcdWM3OTBcdWM1ZjBcdWMyMThcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IDdcdWM3NDQgMlx1Yzc1OCBcdWJhNzFcdWMyMThcdWM3NTggXHVkNTY5XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViMjk0IFx1YjJlNFx1Yzc0Y1x1Yzc1OCBcdWM1ZWNcdWMxMmYgXHVhYzAwXHVjOWMwXHVhYzAwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT4xKzErMSsxKzErMSsxPFwvbGk+XHJcblx0PGxpPjErMSsxKzErMSsyPFwvbGk+XHJcblx0PGxpPjErMSsxKzIrMjxcL2xpPlxyXG5cdDxsaT4xKzErMSs0PFwvbGk+XHJcblx0PGxpPjErMisyKzI8XC9saT5cclxuXHQ8bGk+MSsyKzQ8XC9saT5cclxuPFwvb2w+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOKDEgJmxlOyBOICZsZTsgMSwwMDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViMmY1XHVjNzc0IFx1Y2VlNFx1YzljOCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYmMwXHViODVjIDEsMDAwLDAwMCwwMDBcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjQxMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlN1bXNldHMiLCJkZXNjcmlwdGlvbiI6IjxwPkZhcm1lciBKb2huIGNvbW1hbmRlZCBoaXMgY293cyB0byBzZWFyY2ggZm9yIGRpZmZlcmVudCBzZXRzIG9mIG51bWJlcnMgdGhhdCBzdW0gdG8gYSBnaXZlbiBudW1iZXIuIFRoZSBjb3dzIHVzZSBvbmx5IG51bWJlcnMgdGhhdCBhcmUgYW4gaW50ZWdlciBwb3dlciBvZiAyLiBIZXJlIGFyZSB0aGUgcG9zc2libGUgc2V0cyBvZiBudW1iZXJzIHRoYXQgc3VtIHRvIDc6PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+MSsxKzErMSsxKzErMTxcL2xpPlxyXG5cdDxsaT4xKzErMSsxKzErMjxcL2xpPlxyXG5cdDxsaT4xKzErMSsyKzI8XC9saT5cclxuXHQ8bGk+MSsxKzErNDxcL2xpPlxyXG5cdDxsaT4xKzIrMisyPFwvbGk+XHJcblx0PGxpPjErMis0PFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+SGVscCBGSiBjb3VudCBhbGwgcG9zc2libGUgcmVwcmVzZW50YXRpb25zIGZvciBhIGdpdmVuIGludGVnZXIgTiAoMSAmbHQ7PSBOICZsdDs9IDEsMDAwLDAwMCkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5BIHNpbmdsZSBsaW5lIHdpdGggYSBzaW5nbGUgaW50ZWdlciwgTi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgbnVtYmVyIG9mIHdheXMgdG8gcmVwcmVzZW50IE4gYXMgdGhlIGluZGljYXRlZCBzdW0uIER1ZSB0byB0aGUgcG90ZW50aWFsIGh1Z2Ugc2l6ZSBvZiB0aGlzIG51bWJlciwgcHJpbnQgb25seSBsYXN0IDkgZGlnaXRzIChpbiBiYXNlIDEwIHJlcHJlc2VudGF0aW9uKS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d