시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1114 612 445 58.707%

문제

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+XHJcblxyXG48cD5cdWM4ODVcdWMyMThcdWIyOTQgXHVjMTkwXHViMTQwXHVjNWQwXHVhYzhjIFx1ZDU1YyBcdWM4NzBcdWFjMDFcdWM3NDQgXHVhZWJjXHViMGI4IFx1YjBhMFx1YzVkMFx1YjI5NCBXXHViOTdjLCBcdWJjMTggXHVjODcwXHVhYzAxXHVjNzQ0IFx1YWViY1x1YjBiOCBcdWIwYTBcdWM1ZDBcdWIyOTQgSCBcdWJjZjRcdWIwYjhcdWIyZTQuIFx1YzE5MFx1YjE0MFx1YjI5NCBcdWQ1NjBcdWM1NDRcdWJjODRcdWM5YzBcdWM1ZDBcdWFjOGMgXHViYzFiXHVjNzQwIFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWM4ODVcdWM3NzRcdWM1ZDAgXHVhZTMwXHViODVkXHVkNTc0IFx1YjE5M1x1YjI5NFx1YjJlNC4gXHVjZDFkIDJOXHVjNzdjXHVjNzc0IFx1YzljMFx1YjA5OFx1YmE3NCBcdWFlMzhcdWM3NzRcdWFjMDAgMk5cdWM3NzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YjljY1x1YjRlNFx1YzViNFx1YzljMFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgXHVjZDFkIFx1YmE4NyBcdWFjMWNcdWM3N2NcdWFlNGM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjZDVjXHViMzAwIDEwMDBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHVjNzc0XHViYTcwLCBcdWJjZDFcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzU3ZFx1Yzc1OCBcdWFjMWNcdWMyMTggTiAmbGU7IDMwIFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHVkNTU4XHViMDk4IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQ4MTEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQaWxscyIsImRlc2NyaXB0aW9uIjoiPHA+QXVudCBMaXp6aWUgdGFrZXMgaGFsZiBhIHBpbGwgb2YgYSBjZXJ0YWluIG1lZGljaW5lIGV2ZXJ5IGRheS4gU2hlIHN0YXJ0cyB3aXRoIGEgYm90dGxlIHRoYXQgY29udGFpbnMgTiBwaWxscy48XC9wPlxyXG5cclxuPHA+T24gdGhlIGZpcnN0IGRheSwgc2hlIHJlbW92ZXMgYSByYW5kb20gcGlsbCwgYnJlYWtzIGl0IGluIHR3byBoYWx2ZXMsIHRha2VzIG9uZSBoYWxmIGFuZCBwdXRzIHRoZSBvdGhlciBoYWxmIGJhY2sgaW50byB0aGUgYm90dGxlLjxcL3A+XHJcblxyXG48cD5PbiBzdWJzZXF1ZW50IGRheXMsIHNoZSByZW1vdmVzIGEgcmFuZG9tIHBpZWNlICh3aGljaCBjYW4gYmUgZWl0aGVyIGEgd2hvbGUgcGlsbCBvciBoYWxmIGEgcGlsbCkgZnJvbSB0aGUgYm90dGxlLiBJZiBpdCBpcyBoYWxmIGEgcGlsbCwgc2hlIHRha2VzIGl0LiBJZiBpdCBpcyBhIHdob2xlIHBpbGwsIHNoZSB0YWtlcyBvbmUgaGFsZiBhbmQgcHV0cyB0aGUgb3RoZXIgaGFsZiBiYWNrIGludG8gdGhlIGJvdHRsZS48XC9wPlxyXG5cclxuPHA+SW4gaG93IG1hbnkgd2F5cyBjYW4gc2hlIGVtcHR5IHRoZSBib3R0bGU/IFdlIHJlcHJlc2VudCB0aGUgc2VxdWVuY2Ugb2YgcGlsbHMgcmVtb3ZlZCBmcm9tIHRoZSBib3R0bGUgaW4gdGhlIGNvdXJzZSBvZiAyTiBkYXlzIGFzIGEgc3RyaW5nLCB3aGVyZSB0aGUgaS10aCBjaGFyYWN0ZXIgaXMgVyBpZiBhIHdob2xlIHBpbGwgd2FzIGNob3NlbiBvbiB0aGUgaS10aCBkYXksIGFuZCBIIGlmIGEgaGFsZiBwaWxsIHdhcyBjaG9zZW4gKDAgJmx0Oz0gaSAmbHQ7IDJOKS4gSG93IG1hbnkgZGlmZmVyZW50IHZhbGlkIHN0cmluZ3MgYXJlIHRoZXJlIHRoYXQgZW1wdHkgdGhlIGJvdHRsZT88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCB3aWxsIGNvbnRhaW4gZGF0YSBmb3IgYXQgbW9zdCAxMDAwIHByb2JsZW0gaW5zdGFuY2VzLiBGb3IgZWFjaCBwcm9ibGVtIGluc3RhbmNlIHRoZXJlIHdpbGwgYmUgb25lIGxpbmUgb2YgaW5wdXQ6IGEgcG9zaXRpdmUgaW50ZWdlciBOICZsdDs9IDMwLCB0aGUgbnVtYmVyIG9mIHBpbGxzIGluaXRpYWxseSBpbiB0aGUgYm90dGxlLiBFbmQgb2YgaW5wdXQgd2lsbCBiZSBpbmRpY2F0ZWQgYnkgMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBwcm9ibGVtIGluc3RhbmNlLCB0aGUgb3V0cHV0IHdpbGwgYmUgYSBzaW5nbGUgbnVtYmVyLCBkaXNwbGF5ZWQgYXQgdGhlIGJlZ2lubmluZyBvZiBhIG5ldyBsaW5lLiBJdCB3aWxsIGJlIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHdheXMgdGhlIGJvdHRsZSBjYW4gYmUgZW1wdGllZC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=