21071번 - Long Grid Covering 다국어

문제

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$.

제한

힌트