시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB57251762145431.356%

문제

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

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

입력

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

출력

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

제한

  • 0 ≤ n ≤ 250

예제 입력 1

2
8
12
100
200

예제 출력 1

3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251
W3sicHJvYmxlbV9pZCI6IjE3OTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwYzBcdWM3N2NcdWI5YzEiLCJkZXNjcmlwdGlvbiI6IjxwPjImdGltZXM7biBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgMiZ0aW1lczsxXHVhY2ZjIDImdGltZXM7MiBcdWQwYzBcdWM3N2NcdWI4NWMgXHVjYzQ0XHVjNmIwXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NDAgMiZ0aW1lczsxNyBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjYzQ0XHVjNmI0IFx1ZDU1Y1x1YWMwMFx1YzljMCBcdWM2MDhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdDJuMjEyMi5naWZcIiBzdHlsZT1cImhlaWdodDo1OXB4OyB3aWR0aDozODBweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YzgxNVx1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YWMwMVx1YWMwMVx1Yzc1OCBuXHViOWM4XHViMmU0LCAyJnRpbWVzO24gXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1Y2M0NFx1YzZiMFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MCAmbGU7IG4gJmxlOyAyNTA8XC9saT5cclxuPFwvdWw+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjE3OTMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaWxpbmciLCJkZXNjcmlwdGlvbiI6IjxwPkluIGhvdyBtYW55IHdheXMgY2FuIHlvdSB0aWxlIGEgMnhuIHJlY3RhbmdsZSBieSAyeDEgb3IgMngyIHRpbGVzPzxcL3A+XHJcblxyXG48cD5IZXJlIGlzIGEgc2FtcGxlIHRpbGluZyBvZiBhIDJ4MTcgcmVjdGFuZ2xlLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3QybjIxMjIuZ2lmXCIgc3R5bGU9XCJoZWlnaHQ6NTlweDsgd2lkdGg6MzgwcHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IGlzIGEgc2VxdWVuY2Ugb2YgbGluZXMsIGVhY2ggbGluZSBjb250YWluaW5nIGFuIGludGVnZXIgbnVtYmVyIDAgJmx0Oz0gbiAmbHQ7PSAyNTAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggbGluZSBvZiBpbnB1dCwgb3V0cHV0IG9uZSBpbnRlZ2VyIG51bWJlciBpbiBhIHNlcGFyYXRlIGxpbmUgZ2l2aW5nIHRoZSBudW1iZXIgb2YgcG9zc2libGUgdGlsaW5ncyBvZiBhIDJ4biByZWN0YW5nbGUuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=