23256번 - 성인 게임

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

칼의 칼날은 $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$로 나눈 나머지를 출력하라.

• $1 \leq T \leq 1\,000$
• $1 \leq  N \leq 1\,000\,000$