시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1420 769 561 57.245%

문제

70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.

첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.

다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다.

종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다. 이때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까?

입력

입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서 가능한 문자열의 개수를 출력한다.

예제 입력 1

6
1
4
2
3
30
0

예제 출력 1

132
1
14
2
5
3814986502092304
W3sicHJvYmxlbV9pZCI6IjQ4MTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NGNcdWM1N2QiLCJkZXNjcmlwdGlvbiI6IjxwPjcwXHVjMTM4IFx1YmMxNVx1Yzg4NVx1YzIxOCBcdWQ1NjBcdWM1NDRcdWJjODRcdWM5YzBcdWIyOTQgXHViOWU0XHVjNzdjIFx1YjllNFx1Yzc3YyBcdWM1N2QgXHViYzE4XHVjNTRjXHVjNzQ0IFx1YmEzOVx1YjI5NFx1YjJlNC4gXHVjMTkwXHViMTQwIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWM4ODVcdWMyMTggXHVkNTYwXHVjNTQ0XHViYzg0XHVjOWMwXHVjNWQwXHVhYzhjIFx1YzU3ZFx1Yzc3NCBOXHVhYzFjIFx1YjJmNFx1YWUzNCBcdWJjZDFcdWM3NDQgXHVjMTIwXHViYjNjXHViODVjIFx1YzhmY1x1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjY2FiXHVjOWY4IFx1YjBhMFx1YzVkMCBcdWM4ODVcdWMyMThcdWIyOTQgXHViY2QxXHVjNWQwXHVjMTFjIFx1YzU3ZCBcdWQ1NThcdWIwOThcdWI5N2MgXHVhZWJjXHViMGI4XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjLCBcdWFkZjggXHVjNTdkXHVjNzQ0IFx1YmMxOFx1YzczY1x1Yjg1YyBcdWNhYmNcdWFjMWNcdWMxMWMgXHVkNTVjIFx1Yzg3MFx1YWMwMVx1Yzc0MCBcdWJhMzlcdWFjZTAsIFx1YjJlNFx1Yjk3OCBcdWM4NzBcdWFjMDFcdWM3NDAgXHViMmU0XHVjMmRjIFx1YmNkMVx1YzVkMCBcdWIxMjNcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWIwYTBcdWJkODBcdWQxMzAgXHVjODg1XHVjMjE4XHViMjk0IFx1YmNkMVx1YzVkMFx1YzExYyBcdWM1N2RcdWM3NDQgXHVkNTU4XHViMDk4IFx1YWViY1x1YjBiOFx1YjJlNC4gKFx1YzU3ZFx1Yzc0MCBcdWQ1NWMgXHVjODcwXHVhYzAxIFx1YzgwNFx1Y2NiNCBcdWM3N2MgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YWNlMCwgXHVjYWJjXHVhYzIwIFx1YmMxOCBcdWM4NzBcdWFjMDEgXHVjNzdjIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQpIFx1YmMxOCBcdWM4NzBcdWFjMDFcdWM3NzRcdWI3N2NcdWJhNzQgXHVhZGY4IFx1YzU3ZFx1Yzc0NCBcdWJhMzlcdWFjZTAsIFx1YzU0NFx1YjJjOFx1Yjc3Y1x1YmE3NCBcdWJjMThcdWM3NDQgXHVjYWJjXHVhYzFjXHVjMTFjIFx1ZDU1YyBcdWM4NzBcdWFjMDFcdWM3NDQgXHViYTM5XHVhY2UwLCBcdWIyZTRcdWI5NzggXHVjODcwXHVhYzAxXHVjNzQwIFx1YjJlNFx1YzJkYyBcdWJjZDFcdWM1ZDAgXHViMTIzXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4ODVcdWMyMThcdWIyOTQgXHVjMTkwXHViMTQwXHVjNWQwXHVhYzhjIFx1ZDU1YyBcdWM4NzBcdWFjMDFcdWM3NDQgXHVhZWJjXHViMGI4IFx1YjBhMFx1YzVkMFx1YjI5NCBXXHViOTdjLCBcdWJjMTggXHVjODcwXHVhYzAxXHVjNzQ0IFx1YWViY1x1YjBiOCBcdWIwYTBcdWM1ZDBcdWIyOTQgSCBcdWJjZjRcdWIwYjhcdWIyZTQuIFx1YzE5MFx1YjE0MFx1YjI5NCBcdWQ1NjBcdWM1NDRcdWJjODRcdWM5YzBcdWM1ZDBcdWFjOGMgXHViYzFiXHVjNzQwIFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWM4ODVcdWM3NzRcdWM1ZDAgXHVhZTMwXHViODVkXHVkNTc0IFx1YjE5M1x1YjI5NFx1YjJlNC4gXHVjZDFkIDJOXHVjNzdjXHVjNzc0IFx1YzljMFx1YjA5OFx1YmE3NCBcdWFlMzhcdWM3NzRcdWFjMDAgMk5cdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YjljY1x1YjRlNFx1YzViNFx1YzljMFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVhYzAwXHViMmE1XHVkNTVjIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCBcdWNkMWQgXHViYTg3IFx1YWMxY1x1Yzc3Y1x1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWNkNWNcdWIzMDAgMTAwMFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWM3NzRcdWJhNzAsIFx1YmNkMVx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjNTdkXHVjNzU4IFx1YWMxY1x1YzIxOCBOICZsZTsgMzAgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDgxMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBpbGxzIiwiZGVzY3JpcHRpb24iOiI8cD5BdW50IExpenppZSB0YWtlcyBoYWxmIGEgcGlsbCBvZiBhIGNlcnRhaW4gbWVkaWNpbmUgZXZlcnkgZGF5LiBTaGUgc3RhcnRzIHdpdGggYSBib3R0bGUgdGhhdCBjb250YWlucyBOIHBpbGxzLjxcL3A+XHJcblxyXG48cD5PbiB0aGUgZmlyc3QgZGF5LCBzaGUgcmVtb3ZlcyBhIHJhbmRvbSBwaWxsLCBicmVha3MgaXQgaW4gdHdvIGhhbHZlcywgdGFrZXMgb25lIGhhbGYgYW5kIHB1dHMgdGhlIG90aGVyIGhhbGYgYmFjayBpbnRvIHRoZSBib3R0bGUuPFwvcD5cclxuXHJcbjxwPk9uIHN1YnNlcXVlbnQgZGF5cywgc2hlIHJlbW92ZXMgYSByYW5kb20gcGllY2UgKHdoaWNoIGNhbiBiZSBlaXRoZXIgYSB3aG9sZSBwaWxsIG9yIGhhbGYgYSBwaWxsKSBmcm9tIHRoZSBib3R0bGUuIElmIGl0IGlzIGhhbGYgYSBwaWxsLCBzaGUgdGFrZXMgaXQuIElmIGl0IGlzIGEgd2hvbGUgcGlsbCwgc2hlIHRha2VzIG9uZSBoYWxmIGFuZCBwdXRzIHRoZSBvdGhlciBoYWxmIGJhY2sgaW50byB0aGUgYm90dGxlLjxcL3A+XHJcblxyXG48cD5JbiBob3cgbWFueSB3YXlzIGNhbiBzaGUgZW1wdHkgdGhlIGJvdHRsZT8gV2UgcmVwcmVzZW50IHRoZSBzZXF1ZW5jZSBvZiBwaWxscyByZW1vdmVkIGZyb20gdGhlIGJvdHRsZSBpbiB0aGUgY291cnNlIG9mIDJOIGRheXMgYXMgYSBzdHJpbmcsIHdoZXJlIHRoZSBpLXRoIGNoYXJhY3RlciBpcyBXIGlmIGEgd2hvbGUgcGlsbCB3YXMgY2hvc2VuIG9uIHRoZSBpLXRoIGRheSwgYW5kIEggaWYgYSBoYWxmIHBpbGwgd2FzIGNob3NlbiAoMCAmbHQ7PSBpICZsdDsgMk4pLiBIb3cgbWFueSBkaWZmZXJlbnQgdmFsaWQgc3RyaW5ncyBhcmUgdGhlcmUgdGhhdCBlbXB0eSB0aGUgYm90dGxlPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IHdpbGwgY29udGFpbiBkYXRhIGZvciBhdCBtb3N0IDEwMDAgcHJvYmxlbSBpbnN0YW5jZXMuIEZvciBlYWNoIHByb2JsZW0gaW5zdGFuY2UgdGhlcmUgd2lsbCBiZSBvbmUgbGluZSBvZiBpbnB1dDogYSBwb3NpdGl2ZSBpbnRlZ2VyIE4gJmx0Oz0gMzAsIHRoZSBudW1iZXIgb2YgcGlsbHMgaW5pdGlhbGx5IGluIHRoZSBib3R0bGUuIEVuZCBvZiBpbnB1dCB3aWxsIGJlIGluZGljYXRlZCBieSAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHByb2JsZW0gaW5zdGFuY2UsIHRoZSBvdXRwdXQgd2lsbCBiZSBhIHNpbmdsZSBudW1iZXIsIGRpc3BsYXllZCBhdCB0aGUgYmVnaW5uaW5nIG9mIGEgbmV3IGxpbmUuIEl0IHdpbGwgYmUgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgd2F5cyB0aGUgYm90dGxlIGNhbiBiZSBlbXB0aWVkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==