성인 게임

시간 제한1초메모리 제한1024 MB

요약

한 칸씩 겹치는 2x2 정사각형 N개로 이루어진 칼날 모양을 1x1과 2x1 조각으로 빈틈없이 채우는 경우의 수를 1e9+7로 나눈 나머지를 구한다.

문제

채완이가 좋아하는 성인 게임에는 칼 아이템이 있다.

칼의 칼날은 $2\times 2$ 크기의 정사각형 $N$ 개가 한 칸씩 맞물려 연결되어 있는 형태이다.

아래는 $N = 6$ 일 때의 칼날을 나타낸 그림이다.

칼날은 $1\times 1$ , $2\times 1$ 크기의 광석을 겹치지 않고 빈 칸이 없도록 적절히 붙여 만들 수 있다.

$N$ 이 주어질 때 만들 수 있는 서로 다른 칼날의 개수를 구하는 프로그램을 작성하시오.

광석은 어떤 경우에도 모자라지 않을 만큼 충분히 존재한다.

$2 \times 1$ , $1 \times 1$ 크기의 광석은 각각 다음과 같고 회전시킬 수 있다.

첫째 줄에 테스트 케이스의 수 $T$ 가 주어진다.

이후 $T$ 개의 줄에 걸쳐 $N$ 이 주어진다.

각 테스트 케이스마다 만들 수 있는 서로 다른 칼날의 개수를 $1\,000\,000\,007$ 로 나눈 나머지를 출력하라.