C. DGeneral Hamilton's Cubes
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

DGeneral Hamilton has $$$n^3$$$ small cubes of dimensions $$$1 \times 1 \times 1$$$. Each small cube has six faces numbered with the integers from $$$1$$$ to $$$6$$$, with each number appearing exactly once. The arrangement of these numbers on the faces is the same for all cubes (the small cubes are identical).

DGeneral Hamilton wants to build a large cube of dimensions $$$n \times n \times n$$$ using these small cubes. The large cube will also have $$$6$$$ faces, numbered from $$$1$$$ to $$$6$$$, with each number appearing exactly once. Each face will consist of $$$n \times n$$$ visible squares, where each visible square shows the number on the corresponding face of the small cube placed there.

DGeneral Hamilton wants to know, how many different large cubes can he form?

Two large cubes are considered different if there is at least one face and at least one visible square on that face where the number on that square is different between the two cubes. Remember that the faces are numbered.

Print the answer modulo $$$10^9 + 7$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

Each of the next $$$t$$$ lines contains one integer $$$n$$$ ($$$1 \le n \le 10^9$$$) — the dimension of the large cube DGeneral Hamilton wants to build. He has exactly $$$n^3$$$ small cubes.

Output

For each test case, print a single integer — the number of different large cubes that can be formed modulo $$$10^9 + 7$$$.

Example
Input
2
1
2
Output
24
75313406