L. Long Grid Covering
time limit per test
2 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

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

Input

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.

Output

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

Example
Input
3
1
2
3
Output
1
3
10