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