Problem Description

　　A lattice point is a point with integer coordinates. A lattice triangle is a triangle with all vertices lattice points.
　　Now your task is to calculate how many lattice triangles are there, under the condition that each of its vertex (x, y) satisfies 0 <= x <= N and 0 <= y <= N.
　　We say two triangles are different if and only if they have at least one different vertex.

Input

　　There is an integer T (1 <= T <= 1000) in the first line, which indicates there are T test cases in total.
　　For each test case, there is only one integer N (1 <= N <= 100000) which has the same meaning as above.
There are at most 10 test cases that satisfy N > 1000.

Output

　　For each test case, you should output the correct answer of the above task in one line.
　　Because the answer may be very large, you should just output the remainder of it divided by 1000000007 instead.

3
1
2
100000

4
76
157621156

Hint

For sample 2: We can get the correct answer by calculating C(9, 3) - 8.