시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 182 86 71 62.832%

문제

icpc 왕국에는 아주 못된 왕 유빈이가 있었다.

유빈이에게는 4×n 크키의 카펫이 하나 있었다.

유빈이는 신하들에게 이 카펫을 3×1 타일과 1×3 타일로 빈틈없이 메우라는 명령을 내렸다.

여러분이 신하들을 도와서 4×n 크기의 카펫을 3×1 타일과 1×3 타일로 메우는 방법의 수를  구하는 프로그램을 작성하시오.

입력

첫째 줄에는 테스트 케이스의 수 T가 주어진다. (1 <= T <= 100)

그 다음 T개의 줄에는 카펫에 가로 길이 N이 주어진다. (세로 길이는 4) (1 <= N <= 10,000)

출력

각 테스트 케이스마다 문제의 정답을 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

3
3
6
3333

예제 출력 1

3
13
524313417
W3sicHJvYmxlbV9pZCI6IjExMzMzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiNFx1MDBkN24gXHVkMGMwXHVjNzdjXHViOWMxIiwiZGVzY3JpcHRpb24iOiI8cD5pY3BjIFx1YzY1NVx1YWQ2ZFx1YzVkMFx1YjI5NCBcdWM1NDRcdWM4ZmMgXHViYWJiXHViNDFjIFx1YzY1NSBcdWM3MjBcdWJlNDhcdWM3NzRcdWFjMDAgXHVjNzg4XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3MjBcdWJlNDhcdWM3NzRcdWM1ZDBcdWFjOGNcdWIyOTQgNCZ0aW1lcztuIFx1ZDA2Y1x1ZDBhNFx1Yzc1OCBcdWNlNzRcdWQzYWJcdWM3NzQgXHVkNTU4XHViMDk4IFx1Yzc4OFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzIwXHViZTQ4XHVjNzc0XHViMjk0IFx1YzJlMFx1ZDU1OFx1YjRlNFx1YzVkMFx1YWM4YyBcdWM3NzQgXHVjZTc0XHVkM2FiXHVjNzQ0IDMmdGltZXM7MSBcdWQwYzBcdWM3N2NcdWFjZmMgMSZ0aW1lczszIFx1ZDBjMFx1Yzc3Y1x1Yjg1YyBcdWJlNDhcdWQyYzhcdWM1YzZcdWM3NzQgXHViYTU0XHVjNmIwXHViNzdjXHViMjk0IFx1YmE4NVx1YjgzOVx1Yzc0NCBcdWIwYjRcdWI4MzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzVlY1x1YjdlY1x1YmQ4NFx1Yzc3NCBcdWMyZTBcdWQ1NThcdWI0ZTRcdWM3NDQgXHViM2M0XHVjNjQwXHVjMTFjIDQmdGltZXM7biBcdWQwNmNcdWFlMzBcdWM3NTggXHVjZTc0XHVkM2FiXHVjNzQ0IDMmdGltZXM7MSBcdWQwYzBcdWM3N2NcdWFjZmMgMSZ0aW1lczszIFx1ZDBjMFx1Yzc3Y1x1Yjg1YyBcdWJhNTRcdWM2YjBcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyZuYnNwOyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsdDs9IFQgJmx0Oz0gMTAwKTxcL3A+XHJcblxyXG48cD5cdWFkZjggXHViMmU0XHVjNzRjIFRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2U3NFx1ZDNhYlx1YzVkMCBcdWFjMDBcdWI4NWMgXHVhZTM4XHVjNzc0IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoXHVjMTM4XHViODVjIFx1YWUzOFx1Yzc3NFx1YjI5NCA0KSAoMSAmbHQ7PSBOICZsdDs9IDEwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODE1XHViMmY1XHVjNzQ0IDEsMDAwLDAwMCwwMDdcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMTMzMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvdW50aW5nIEFnYWluPyIsImRlc2NyaXB0aW9uIjoiPHA+R2l2ZW4gYW4gaW50ZWdlciBOLCBpbiBob3cgbWFueSB3YXlzIHlvdSBjYW4gdGlsZSBhIDQgeCBOIHJlY3RhbmdsZSB3aXRoIDMgeCAxIHRpbGVzPyBCZWNhdXNlIHRoZSBhbnN3ZXIgY2FuIGJlIGxhcmdlLCB3ZSBhcmUgaW50ZXJlc3RlZCBpbiB0aGUgcmVtYWluZGVyIGFmdGVyIGFuc3dlciBpcyBkaXZpZGVkIGJ5IDEsMDAwLDAwMCwwMDcuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5GaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIFQgKDEgJmx0Oz0gVCAmbHQ7PSAxMDApIC0gdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBjb25zaXN0IG9mIGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyBhbiBpbnRlZ2VyIE4gKDEgJmx0Oz0gTiAmbHQ7PSAxMCwwMDApLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBwcmludCB0aGUgdGhlIHJlbWFpbmRlciBhZnRlciBhbnN3ZXIgaXMgZGl2aWRlZCBieSAxLDAwMCwwMDAsMDA3LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > Calgary Collegiate Programming Contest > CCPC 2013 B번