Unique Square Gardens

In this problem, you are given an integer M representing the side length of a square grid, and you need to calculate the total number of square sub-grids (or "unique square gardens") contained within an M x M grid. A square sub-grid of size s x s can start at any location within the grid where it fits completely. Thus, for a given s, there are (M - s + 1)^2 possible positions. The overall answer is the sum of these counts for s = 1 to M, taken modulo 1000000007. The formula is given by:

$$\text{result} = \sum_{s=1}^{M} (M - s + 1)^2 \pmod{1000000007} $$

Your task is to process multiple test cases. For each test case, output the corresponding count of unique square gardens.

inputFormat

The first line of input contains an integer T representing the number of test cases. Each of the following T lines contains a single integer M (1 ≤ M ≤ 10^9) that denotes the grid size.

outputFormat

For each test case, output the result in a separate line which is the number of unique square gardens in an M x M grid modulo 1000000007.

## sample

2
2
3

5
14

</p>