Description

Give you a cube with a side length of n-1. Find the number of equilateral triangles with three points on the cube point.
Each side must be parallel to a certain surface of Oxy, Oxz, Oyz. Now you need to count how many such triangles there are.
Each point can only be on the boundary or inner point of the cube, and the three coordinates x, y, and z of each point must be integers.

Format

Input

The first line contains an integer $T(T<=10^5)$ . Then T test cases follow.

Each test case contains a single Integer $n(0<=n<=10^{18})$.

If $n=0$, output $0$

Output

For each case, print an integer, which is the answer modulo $10^9+7$

Samples

2
1
2

0
8