시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2291 645 531 29.966%

문제

2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다. 

출력

입력으로 주어지는 각각의 n마다, 2×n 직사각형을 채우는 방법의 수를 출력한다.

예제 입력 1

2
8
12
100
200

예제 출력 1

3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251

힌트

W3sicHJvYmxlbV9pZCI6IjE3OTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwYzBcdWM3N2NcdWI5YzEiLCJkZXNjcmlwdGlvbiI6IjxwPjImdGltZXM7biBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgMiZ0aW1lczsxXHVhY2ZjIDImdGltZXM7MiBcdWQwYzBcdWM3N2NcdWI4NWMgXHVjYzQ0XHVjNmIwXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NDAgMiZ0aW1lczsxNyBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjYzQ0XHVjNmI0IFx1ZDU1Y1x1YWMwMFx1YzljMCBcdWM2MDhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdDJuMjEyMi5naWZcIiBzdHlsZT1cImhlaWdodDo1OXB4OyB3aWR0aDozODBweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YzIyYlx1Yzc5MCAwICZsZTsgbiAmbGU7IDI1MFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWFjMDFcdWFjMDFcdWM3NTggblx1YjljOFx1YjJlNCwgMiZ0aW1lcztuIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWNjNDRcdWM2YjBcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTc5MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRpbGluZyIsImRlc2NyaXB0aW9uIjoiPHA+SW4gaG93IG1hbnkgd2F5cyBjYW4geW91IHRpbGUgYSAyeG4gcmVjdGFuZ2xlIGJ5IDJ4MSBvciAyeDIgdGlsZXM/PFwvcD5cclxuXHJcbjxwPkhlcmUgaXMgYSBzYW1wbGUgdGlsaW5nIG9mIGEgMngxNyByZWN0YW5nbGUuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdDJuMjEyMi5naWZcIiBzdHlsZT1cImhlaWdodDo1OXB4OyB3aWR0aDozODBweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgaXMgYSBzZXF1ZW5jZSBvZiBsaW5lcywgZWFjaCBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciBudW1iZXIgMCAmbHQ7PSBuICZsdDs9IDI1MC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBsaW5lIG9mIGlucHV0LCBvdXRwdXQgb25lIGludGVnZXIgbnVtYmVyIGluIGEgc2VwYXJhdGUgbGluZSBnaXZpbmcgdGhlIG51bWJlciBvZiBwb3NzaWJsZSB0aWxpbmdzIG9mIGEgMnhuIHJlY3RhbmdsZS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d