Cho một lưới hình ô vuông có kích thước \(n \times n\). Đếm số lượng hình vuông có trong hình đó.

Input

• Dòng đầu ghi \(q\) không quá \(100\) - số câu hỏi.
• \(q\) dòng tiếp theo, mỗi dòng ghi \(n\) không quá \(10^9\)

Output

• Ứng với mỗi câu hỏi, in ra kết quả cần tìm sau khi \(\mod \left( 10^9 + 7 \right)\)

Example

1
1

1