시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 46 30 22 91.667%

문제

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+XHJcblxyXG48cD5cdWFkZjggXHViMmU0XHVjNzRjIFRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2U3NFx1ZDNhYlx1YzVkMCBcdWFjMDBcdWI4NWMgXHVhZTM4XHVjNzc0IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoXHVjMTM4XHViODVjIFx1YWUzOFx1Yzc3NFx1YjI5NCA0KSAoMSAmbHQ7PSBOICZsdDs9IDEwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODE1XHViMmY1XHVjNzQ0IDEsMDAwLDAwMCwwMDdcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTEzMzMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb3VudGluZyBBZ2Fpbj8iLCJkZXNjcmlwdGlvbiI6IjxwPkdpdmVuIGFuIGludGVnZXIgTiwgaW4gaG93IG1hbnkgd2F5cyB5b3UgY2FuIHRpbGUgYSA0IHggTiByZWN0YW5nbGUgd2l0aCAzIHggMSB0aWxlcz8gQmVjYXVzZSB0aGUgYW5zd2VyIGNhbiBiZSBsYXJnZSwgd2UgYXJlIGludGVyZXN0ZWQgaW4gdGhlIHJlbWFpbmRlciBhZnRlciBhbnN3ZXIgaXMgZGl2aWRlZCBieSAxLDAwMCwwMDAsMDA3LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+Rmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgYW4gaW50ZWdlciBUICgxICZsdDs9IFQgJmx0Oz0gMTAwKSAtIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdCBvZiBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciBOICgxICZsdDs9IE4gJmx0Oz0gMTAsMDAwKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UgcHJpbnQgdGhlIHRoZSByZW1haW5kZXIgYWZ0ZXIgYW5zd2VyIGlzIGRpdmlkZWQgYnkgMSwwMDAsMDAwLDAwNy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Calgary Collegiate Programming Contest > CCPC 2013 B번