Problem G. Pyramid

The use of the triangle in the New Age practices seems to be very important as it represents the unholy trinity (Satan, the Antichrist and the False Prophet bringing mankind to the New World Order with false/distorted beliefs). The triangle is of primary importance in all Illuminati realms, whether in the ritual ceremonies of the Rosicrucians and Masons or the witchcraft, astrological and black magic practices of other Illuminati followers.

One day you found a class of mysterious patterns. The patterns can be classified into different degrees. A pattern of degree nn consists of n(n+1)2\frac{n(n+1)}{2} small regular triangles with side length 1, all in the same direction, forming a big triangle. The figure below shows the pattern of degree 3. All small regular triangles are highlighted.

Since the pattern contains many regular triangles, which is very evil and unacceptable, you want to calculate the number of regular triangles formed by vertices in the pattern, so that you can estimate the strength of Illuminati. It is not necessary that each side of regular triangles is parallel to one side of the triangles. The figure below shows two regular triangles formed by vertices in a pattern of degree 33.

degree 3 example

Since the answer can be very large, you only need to calculate the number modulo 109+710^9 + 7.

Input

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

Each of the next t lines contains an integer n(1≤n≤109)n (1 \le n \le 10^9) — the degree of the pattern.

Output

For each test case, print an integer in one line — the number of regular triangles modulo 109+710^9 + 7.

题意：由n行三角形组成的大三角，其中所有顶点能够组成的三角形的数量是多少，输入n，输出答案mod 1e9+7。

题意很简单，硬数找规律，数出来 1, 5, 15，35，70，126

杨辉三角
发现是杨辉三角上斜着的一行，直接套公式出答案

(n4)=n(n−1)(n−2)(n−3)24\dbinom{n}{4} = \frac{n(n-1)(n-2)(n-3)}{24}

在OEIS上有更多信息:

连接 nn 个顶点的直线能产生的最大交点数
基于4维正单纯形（五胞体）的形数
nn 行等边三角形点阵中等边三角形的数量（任意方向）。(本题)
nn 阶阶梯中的晶格矩形（包括正方形）数量

Codeforces