시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 236 118 84 48.276%

문제

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

어느 날 그는 꿈에서 너비가 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+XHVjNWI0XHViMjkwIFx1YjBhMCBcdWFkZjhcdWIyOTQgXHVhZmM4XHVjNWQwXHVjMTFjIFx1YjEwOFx1YmU0NFx1YWMwMCAyLCBcdWIxOTJcdWM3NzRcdWFjMDAgMVx1Yzc3OCBcdWM3OTFcdWM3NDAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWQwNzAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1Y2M0NFx1YzZiMFx1YjI5NCBcdWFmYzhcdWM3NDQgXHVhZmI4XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2RyZWFtMS5naWZcIiBzdHlsZT1cImhlaWdodDozM3B4OyB3aWR0aDo1OTlweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVkMDZjXHVhZTMwXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjNzkxXHVjNzQwIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWNjNDRcdWM2YjBcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkMDcwIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWIxOTJcdWM3NzQgaFx1YzY0MCBcdWIxMDhcdWJlNDQgd1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YjQ1MCBcdWFjMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IGgsIHcgJmxlOyAxMSk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVkMDcwIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWM3OTFcdWM3NDAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IDIgJnRpbWVzOyAxIFx1Yjg1YyBcdWNjNDRcdWM2YjBcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIChcdWQwNzAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQwIFx1YmMyOVx1ZDVhNVx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1Yzk4OSwgXHViMzAwXHVjZTZkXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YzEzOFx1YzU3YyBcdWQ1NWNcdWIyZTQpPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZHJlYW0yLmdpZlwiIHN0eWxlPVwiaGVpZ2h0OjMxNnB4OyB3aWR0aDozNDhweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNjU2OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1vbmRyaWFhbidzIERyZWFtIiwiZGVzY3JpcHRpb24iOiI8cD5TcXVhcmVzIGFuZCByZWN0YW5nbGVzIGZhc2NpbmF0ZWQgdGhlIGZhbW91cyBEdXRjaCBwYWludGVyIFBpZXQgTW9uZHJpYWFuLiBPbmUgbmlnaHQsIGFmdGVyIHByb2R1Y2luZyB0aGUgZHJhd2luZ3MgaW4gaGlzICYjMzk7dG9pbGV0IHNlcmllcyYjMzk7ICh3aGVyZSBoZSBoYWQgdG8gdXNlIGhpcyB0b2lsZXQgcGFwZXIgdG8gZHJhdyBvbiwgZm9yIGFsbCBvZiBoaXMgcGFwZXIgd2FzIGZpbGxlZCB3aXRoIHNxdWFyZXMgYW5kIHJlY3RhbmdsZXMpLCBoZSBkcmVhbXQgb2YgZmlsbGluZyBhIGxhcmdlIHJlY3RhbmdsZSB3aXRoIHNtYWxsIHJlY3RhbmdsZXMgb2Ygd2lkdGggMiBhbmQgaGVpZ2h0IDEgaW4gdmFyeWluZyB3YXlzLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2RyZWFtMS5naWZcIiBzdHlsZT1cImhlaWdodDozM3B4OyB3aWR0aDo1OTlweFwiIFwvPjxcL3A+XHJcblxyXG48cD5FeHBlcnQgYXMgaGUgd2FzIGluIHRoaXMgbWF0ZXJpYWwsIGhlIHNhdyBhdCBhIGdsYW5jZSB0aGF0IGhlJiMzOTtsbCBuZWVkIGEgY29tcHV0ZXIgdG8gY2FsY3VsYXRlIHRoZSBudW1iZXIgb2Ygd2F5cyB0byBmaWxsIHRoZSBsYXJnZSByZWN0YW5nbGUgd2hvc2UgZGltZW5zaW9ucyB3ZXJlIGludGVnZXIgdmFsdWVzLCBhcyB3ZWxsLiBIZWxwIGhpbSwgc28gdGhhdCBoaXMgZHJlYW0gd29uJiMzOTt0IHR1cm4gaW50byBhIG5pZ2h0bWFyZSE8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBmaWxlIGNvbnRhaW5zIHNldmVyYWwgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgaXMgbWFkZSB1cCBvZiB0d28gaW50ZWdlciBudW1iZXJzOiB0aGUgaGVpZ2h0IGggYW5kIHRoZSB3aWR0aCB3IG9mIHRoZSBsYXJnZSByZWN0YW5nbGUuIElucHV0IGlzIHRlcm1pbmF0ZWQgYnkgaD13PTAuIE90aGVyd2lzZSwgMSZsdDs9aCx3Jmx0Oz0xMS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCB3YXlzIHRoZSBnaXZlbiByZWN0YW5nbGUgY2FuIGJlIGZpbGxlZCB3aXRoIHNtYWxsIHJlY3RhbmdsZXMgb2Ygc2l6ZSAyIHRpbWVzIDEuIEFzc3VtZSB0aGUgZ2l2ZW4gbGFyZ2UgcmVjdGFuZ2xlIGlzIG9yaWVudGVkLCBpLmUuIGNvdW50IHN5bW1ldHJpY2FsIHRpbGluZ3MgbXVsdGlwbGUgdGltZXMuPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZHJlYW0yLmdpZlwiIHN0eWxlPVwiaGVpZ2h0OjMxNnB4OyB3aWR0aDozNDhweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d