시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 892 548 429 63.744%

문제

4*N 크기의 타일을 2*1, 1*2 크기의 도미노로 완전히 채우려고 한다. 예를 들어 4*2 타일을 채우는 방법은 다음과 같이 5가지가 있다.

N이 주어졌을 때, 타일을 채우는 방법의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1,000보다 작거나 같은 자연수이다. 각 테스트 케이스는 정수 하나로 이루어져 있다. 이 정수는 문제에서 설명한 타일의 너비 N이다. N은 자연수이다.

출력

각 테스트 케이스에 대해 4*N크기의 타일을 채우는 방법의 경우의 수를 출력한다.

예제 입력 1

3
2
3
7

예제 출력 1

5 
11 
781

힌트

N제한은 딱히 정해져있지 않다. 하지만, 4*N을 채우는 경우의 수가 int 범위 안에 들어오는 N만 주어진다.

W3sicHJvYmxlbV9pZCI6IjI3MTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwYzBcdWM3N2MgXHVjYzQ0XHVjNmIwXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHQ0Kk4gXHVkMDZjXHVhZTMwXHVjNzU4IFx1ZDBjMFx1Yzc3Y1x1Yzc0NCAyKjEsIDEqMiBcdWQwNmNcdWFlMzBcdWM3NTggXHViM2M0XHViYmY4XHViMTc4XHViODVjIFx1YzY0NFx1YzgwNFx1ZDc4OCBcdWNjNDRcdWM2YjBcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IDQqMiBcdWQwYzBcdWM3N2NcdWM3NDQgXHVjYzQ0XHVjNmIwXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IDVcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL1NjcmVlbiUyMFNob3QlMjAyMDEyLTEwLTA2JTIwYXQlMjAlRUMlOTglQTQlRUMlQTAlODQlMjA2XzEwXzA5LnBuZ1wiIHN0eWxlPVwid2lkdGg6IDMxNXB4OyBoZWlnaHQ6IDEwOXB4OyBcIiBcLz48XC9wPlxyXG5cclxuPHA+XHJcblx0Tlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWQwYzBcdWM3N2NcdWM3NDQgXHVjYzQ0XHVjNmIwXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBUXHViMjk0IDEsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWM4MTVcdWMyMTggXHVkNTU4XHViMDk4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWM4MTVcdWMyMThcdWIyOTQgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YzEyNFx1YmE4NVx1ZDU1YyBcdWQwYzBcdWM3N2NcdWM3NTggXHViMTA4XHViZTQ0IE5cdWM3NzRcdWIyZTQuIE5cdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCA0Kk5cdWQwNmNcdWFlMzBcdWM3NTggXHVkMGMwXHVjNzdjXHVjNzQ0IFx1Y2M0NFx1YzZiMFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlxyXG5cdE5cdWM4MWNcdWQ1NWNcdWM3NDAgXHViNTMxXHVkNzg4IFx1YzgxNVx1ZDU3NFx1YzgzOFx1Yzc4OFx1YzljMCBcdWM1NGFcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgNCpOXHVjNzQ0IFx1Y2M0NFx1YzZiMFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHVhYzAwIGludCBcdWJjOTRcdWM3MDQgXHVjNTQ4XHVjNWQwIFx1YjRlNFx1YzViNFx1YzYyNFx1YjI5NCBOXHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI3MTgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaWxpbmcgYSBHcmlkIFdpdGggRG9taW5vZXMiLCJkZXNjcmlwdGlvbiI6IjxwPldlIHdpc2ggdG8gdGlsZSBhIGdyaWQgNCB1bml0cyBoaWdoIGFuZCBOIHVuaXRzIGxvbmcgd2l0aCByZWN0YW5nbGVzIChkb21pbm9lcykgMiB1bml0cyBieSBvbmUgdW5pdCAoaW4gZWl0aGVyIG9yaWVudGF0aW9uKS4gRm9yIGV4YW1wbGUsIHRoZSBmaWd1cmUgc2hvd3MgdGhlIGZpdmUgZGlmZmVyZW50IHdheXMgdGhhdCBhIGdyaWQgNCB1bml0cyBoaWdoIGFuZCAyIHVuaXRzIHdpZGUgbWF5IGJlIHRpbGVkLiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL1NjcmVlbiUyMFNob3QlMjAyMDEyLTEwLTA2JTIwYXQlMjAlRUMlOTglQTQlRUMlQTAlODQlMjA2XzEwXzA5LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEwOXB4OyB3aWR0aDozMTVweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCB0YWtlcyBhcyBpbnB1dCB0aGUgd2lkdGgsIFcsIG9mIHRoZSBncmlkIGFuZCBvdXRwdXRzIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHdheXMgdG8gdGlsZSBhIDQtYnktVyBncmlkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBOLCAoMSAmbGU7IE4gJmxlOyAxMDAwKSB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGRhdGFzZXRzIHRoYXQgZm9sbG93LiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIGRhdGFzZXQgY29udGFpbnMgYSBzaW5nbGUgZGVjaW1hbCBpbnRlZ2VyLCB0aGUgd2lkdGgsIFcsIG9mIHRoZSBncmlkIGZvciB0aGlzIHByb2JsZW0gaW5zdGFuY2UuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggcHJvYmxlbSBpbnN0YW5jZSwgdGhlcmUgaXMgb25lIGxpbmUgb2Ygb3V0cHV0OiBUaGUgcHJvYmxlbSBpbnN0YW5jZSBudW1iZXIgYXMgYSBkZWNpbWFsIGludGVnZXIgKHN0YXJ0IGNvdW50aW5nIGF0IG9uZSksIGEgc2luZ2xlIHNwYWNlIGFuZCB0aGUgbnVtYmVyIG9mIHRpbGluZ3Mgb2YgYSA0LWJ5LVcgZ3JpZC4gVGhlIHZhbHVlcyBvZiBXIHdpbGwgYmUgY2hvc2VuIHNvIHRoZSBjb3VudCB3aWxsIGZpdCBpbiBhIDMyLWJpdCBpbnRlZ2VyLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==