Count Observable Triangles

In this problem, you are given a convex polygon with n vertices. Your task is to compute the total number of triangles that can be formed by selecting any three vertices from the polygon. Formally, the number of triangles is given by the combination formula:

[ C(n,3)= \frac{n \times (n-1) \times (n-2)}{6} \mod (10^9+7) ]

If n is less than 3, no triangle can be formed, and the answer is 0. The answer for each test case must be computed modulo 1000000007.

This problem tests your ability to handle simple combinatorial computations and modular arithmetic. Read the input from standard input (stdin) and output the results to standard output (stdout).

inputFormat

The first line of the input contains a single integer t (t \ge 1) denoting the number of test cases. The following t lines each contain a single integer n representing the number of vertices in the polygon.

outputFormat

For each test case, output a single line containing the number of triangles that can be observed (i.e., formed) from an n-sided polygon modulo 1000000007.## sample

1
3

1