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}\)