Long Grid Covering

시간 제한2초메모리 제한512 MB

요약

3×n 격자를 세 칸짜리 일자 트로미노로 빈틈없이 채우는 경우의 수를 10^9+7로 나눈 나머지로 구한다. n은 10^18까지 주어진다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 행렬, 조합론, 수학
정답자: 아직 제출이 없습니다

문제

We have a grid of height $3$ and width $n$ , as well as pieces that occupy $3$ adjacent cells. Given $n$ , determine the number of ways to fill the grid so that each cell is covered by exactly one piece and no piece sticks out of the grid. Here there is an example of a way to fill a grid of width $4$ :

Notice that any piece will be a rotation of one of the pieces of this example. Find the answers modulo $10^9 + 7$ .

입력

The first line contains an integer $t$ , the number of test cases ( $1 \leq t \leq 100$ ).

Each test case is given on a separate line containing an integer $n$ ( $1 \leq n \leq 10^{18}$ ), the width of the grid.

출력

For each test case, print a line with a single integer: the number of ways to fill the grid with aforementioned conditions modulo $10^9 + 7$ .

예제1

예제 1
입력
```
3
1
2
3
```
예상 출력
```
1
3
10
```