Nguồn đề: CLB GTLT FITHOU, mọi sự sao chép yêu cầu thêm đường dẫn tới bài tập, xin chân thành cảm ơn.

Có dãy 2, 6, 12, 20, 30, ..., n * (n + 1)

Hãy tính ~f(n)~ với ~f(n)~ bằng :

~ \sum_{i = 1}^{n} f(i*(i+1)) ~

Input

Dòng đầu tiên chứa một số nguyên t - số lượng test ~(1 \le t \le 10^5 )~

t dòng tiếp theo, mỗi dòng chứa 1 số nguyên n ~(1 \le n \le 10^{8} )~

Output

Với mỗi test in ra tổng của phần tử thứ nhất đến phần tử thứ n của dãy, kết quả chia dư với mod = ~ (10^9 + 7)~

Sample Input 1

5
1
2
3
4
100

Sample Output 1

2
8
20
40
343400

Giải thích : n = 2 , 1x(1+1) + 2x(2+1) = 1x2 + 2x3 = 8

10% điểm tương ứng với ~(1 \le t \le 10^3 )~ và ~(1 \le n \le 10^{2} )~

90% điểm tương ứng với ~(1 \le t \le 10^5 )~ và ~(1 \le n \le 10^{8} )~