首先需要能猜到每次「向右+向下」。需要贪心知道2数和相等的时候越接近，乘积越大。

然后就是公式推导：

$$ \sum_{i=1}^{n} i*i + \sum_{i=1}^{n-1}i*(i-1) $$

$$ \frac{n*(n+1)*(2n+1)}{6} + \frac{n*(n-1)*(2n-1)}{6} + \frac{n*(n-1)}{2} = \frac{n*(n+1)*(4n-1)}{6} $$

前提需要知道平方和公式：

$$ \sum_{i=1}^{n}i^2 = \frac{n*(n+1)*(2n+1)}{6} $$

#include<iostream>
 
const long long int mod = 1e9 + 7;
 
int main()
{
	int T;
	std::cin >> T;
	while(T--)
	{
		long long int n, sum = 0;
		std::cin >> n;
		sum = (((n*(n+1)) % mod) * (4 * n - 1) % mod) * 337 % mod;
		std::cout << sum << std::endl;
	}
 
	return 0;
}