Phần tử thứ ~ n ~ trong dãy được tính theo công thức: ~ T_n = n^2 - (n-1)^2 ~.

**Yêu cầu: ** Hãy tính ~ S_n= (T_1 + T_2 + ⋯ + T_n ) mod (10^9+7) ~ Trong đó ~mod~ là phép chia lấy phần dư

Dữ liệu vào

Gồm nhiều bộ dữ liệu:

• Dòng đầu tiên ghi số nguyên dương ~ t ~ ~ (t ≤ 10) ~ cho biết số lượng bộ dữ liệu
• ~ t ~ dòng tiếp theo mỗi dòng ghi một số nguyên dương ~ n ~ ~ (n ≤ 10^{16}) ~

Kết quả

• Với mỗi bộ dữ liệu trong Input, tính và ghi ra giá trị ~ S_n ~ tương ứng, mỗi kết quả ghi trên một dòng.

Ví dụ:

Input 1

2
2
1 

Output 1

4 
1