시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 127 61 44 47.312%

문제

네델란드의 미술 화가 피트 몬드리안은 정사각형과 직사각형에 매료되어 있었다.

어느날 그는 꿈에서 너비가 2, 높이가 1인 작은 직사각형을 이용해서 큰 직사각형을 채우는 꿈을 꾸었다.

직사각형의 크기가 주어졌을 때, 이 직사각형을 작은 직사각형으로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 큰 직사각형의 높이 h와 너비 w로 이루어져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다. (1 ≤ h, w ≤ 11)

출력

각 테스트 케이스에 대해서, 입력으로 주어진 큰 직사각형을 작은 직사각형 2 × 1 로 채우는 방법의 수를 출력한다. (큰 직사각형은 방향이 있다. 즉, 대칭하는 방법을 여러번 세야 한다)

예제 입력 1

1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

예제 출력 1

1
0
1
2
3
5
144
51205

힌트

W3sicHJvYmxlbV9pZCI6IjY1NjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJhYWNcdWI0ZGNcdWI5YWNcdWM1NDhcdWM3NTggXHVhZmM4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIxMjRcdWIzNzhcdWI3ODBcdWI0ZGNcdWM3NTggXHViYmY4XHVjMjIwIFx1ZDY1NFx1YWMwMCBcdWQ1M2NcdWQyYjggXHViYWFjXHViNGRjXHViOWFjXHVjNTQ4XHVjNzQwIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YWNmYyBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM1ZDAgXHViOWU0XHViOGNjXHViNDE4XHVjNWI0IFx1Yzc4OFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViMjkwXHViMGEwIFx1YWRmOFx1YjI5NCBcdWFmYzhcdWM1ZDBcdWMxMWMgXHViMTA4XHViZTQ0XHVhYzAwIDIsIFx1YjE5Mlx1Yzc3NFx1YWMwMCAxXHVjNzc4IFx1Yzc5MVx1Yzc0MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1ZDA3MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjYzQ0XHVjNmIwXHViMjk0IFx1YWZjOFx1Yzc0NCBcdWFmYjhcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZHJlYW0xLmdpZlwiIHN0eWxlPVwiaGVpZ2h0OjMzcHg7IHdpZHRoOjU5OXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWQwNmNcdWFlMzBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWM3OTFcdWM3NDAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzNjXHViODVjIFx1Y2M0NFx1YzZiMFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQwNzAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YjE5Mlx1Yzc3NCBoXHVjNjQwIFx1YjEwOFx1YmU0NCB3XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHViNDUwIFx1YWMxYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgaCwgdyAmbGU7IDExKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWQwNzAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1Yzc5MVx1Yzc0MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgMiAmdGltZXM7IDEgXHViODVjIFx1Y2M0NFx1YzZiMFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gKFx1ZDA3MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgXHViYzI5XHVkNWE1XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjOTg5LCBcdWIzMDBcdWNlNmRcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1YzVlY1x1YjdlY1x1YmM4OCBcdWMxMzhcdWM1N2MgXHVkNTVjXHViMmU0KTxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2RyZWFtMi5naWZcIiBzdHlsZT1cImhlaWdodDozMTZweDsgd2lkdGg6MzQ4cHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjY1NjkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNb25kcmlhYW4ncyBEcmVhbSIsImRlc2NyaXB0aW9uIjoiPHA+U3F1YXJlcyBhbmQgcmVjdGFuZ2xlcyBmYXNjaW5hdGVkIHRoZSBmYW1vdXMgRHV0Y2ggcGFpbnRlciBQaWV0IE1vbmRyaWFhbi4gT25lIG5pZ2h0LCBhZnRlciBwcm9kdWNpbmcgdGhlIGRyYXdpbmdzIGluIGhpcyAmIzM5O3RvaWxldCBzZXJpZXMmIzM5OyAod2hlcmUgaGUgaGFkIHRvIHVzZSBoaXMgdG9pbGV0IHBhcGVyIHRvIGRyYXcgb24sIGZvciBhbGwgb2YgaGlzIHBhcGVyIHdhcyBmaWxsZWQgd2l0aCBzcXVhcmVzIGFuZCByZWN0YW5nbGVzKSwgaGUgZHJlYW10IG9mIGZpbGxpbmcgYSBsYXJnZSByZWN0YW5nbGUgd2l0aCBzbWFsbCByZWN0YW5nbGVzIG9mIHdpZHRoIDIgYW5kIGhlaWdodCAxIGluIHZhcnlpbmcgd2F5cy48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9kcmVhbTEuZ2lmXCIgc3R5bGU9XCJoZWlnaHQ6MzNweDsgd2lkdGg6NTk5cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RXhwZXJ0IGFzIGhlIHdhcyBpbiB0aGlzIG1hdGVyaWFsLCBoZSBzYXcgYXQgYSBnbGFuY2UgdGhhdCBoZSYjMzk7bGwgbmVlZCBhIGNvbXB1dGVyIHRvIGNhbGN1bGF0ZSB0aGUgbnVtYmVyIG9mIHdheXMgdG8gZmlsbCB0aGUgbGFyZ2UgcmVjdGFuZ2xlIHdob3NlIGRpbWVuc2lvbnMgd2VyZSBpbnRlZ2VyIHZhbHVlcywgYXMgd2VsbC4gSGVscCBoaW0sIHNvIHRoYXQgaGlzIGRyZWFtIHdvbiYjMzk7dCB0dXJuIGludG8gYSBuaWdodG1hcmUhPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgZmlsZSBjb250YWlucyBzZXZlcmFsIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGlzIG1hZGUgdXAgb2YgdHdvIGludGVnZXIgbnVtYmVyczogdGhlIGhlaWdodCBoIGFuZCB0aGUgd2lkdGggdyBvZiB0aGUgbGFyZ2UgcmVjdGFuZ2xlLiBJbnB1dCBpcyB0ZXJtaW5hdGVkIGJ5IGg9dz0wLiBPdGhlcndpc2UsIDEmbHQ7PWgsdyZsdDs9MTEuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgd2F5cyB0aGUgZ2l2ZW4gcmVjdGFuZ2xlIGNhbiBiZSBmaWxsZWQgd2l0aCBzbWFsbCByZWN0YW5nbGVzIG9mIHNpemUgMiB0aW1lcyAxLiBBc3N1bWUgdGhlIGdpdmVuIGxhcmdlIHJlY3RhbmdsZSBpcyBvcmllbnRlZCwgaS5lLiBjb3VudCBzeW1tZXRyaWNhbCB0aWxpbmdzIG11bHRpcGxlIHRpbWVzLjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2RyZWFtMi5naWZcIiBzdHlsZT1cImhlaWdodDozMTZweDsgd2lkdGg6MzQ4cHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==