시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB2541138644.103%

문제

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

칼의 칼날은 $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$ 

예제 입력 1

2
1
2

예제 출력 1

7
33

$N = 1$인 서로 다른 칼날은 아래 그림처럼 7개가 있다.

$N = 2$인 서로 다른 칼날은 아래 그림처럼 33개가 있다.