Given an empty grid with $4$ rows and $n$ columns, count the number of ways to fill the grid with 0's and 1's, such that for all the $4$ x $4$ subgrids, they contain an equal amount of 1's in them. Since the number of ways could be quite large, you should find it modulo $10^9 + 7$.

Note: It is possible to have zero 1's in the subgrids.

A subgrid is a grid made up of a subset of the larger grid. 

 Input format

• The first line contains an integer, $t$ - denoting the number of test cases. 
• The next $t$ lines of the input each contain an integer, $n_{i}$ - denoting the number of columns the grid has in the $i^{th}$ test case.

Output format

Your program should output $t$ lines, each line denoting the total number of ways to fill a grid of $4$ rows and $n_{i}$ columns modulo $10^9 + 7$ for the $i^{th}$ test case.

Constraints

$1 \leq t \leq 1000 \\ 4 \leq n_i \leq 10^{18}$