Cho 1 dãy số nguyên dương, tuân theo quy luật sau:

• ~1~ phần tử đầu tiên có giá trị là ~1~.
• ~2~ phần tử tiếp theo có giá trị là ~2~.
• ~3~ phần tử tiếp theo có giá trị là ~3~.
• ~\dots~
• ~m~ phần tử tiếp theo có giá trị là ~m~.

Nói cách khác, dãy số sẽ có dạng ~1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5,\dots~

Cho một số nguyên dương ~n~, hãy tính tổng của ~n~ phần tử đầu tiên trong dãy số trên.

Vì kết quả có thể rất lớn nên hãy lấy kết quả chia dư cho ~10^9+7~.

Dữ liệu vào:

• Dòng đầu tiên chứa một số nguyên dương ~t\ (t\leq 10)~.
• ~t~ dòng tiếp theo, mỗi dòng chứa duy nhất một số nguyên dương ~n\ (n \leq 10^{18})~.

Dữ liệu ra:

• In ra ~t~ dòng, mỗi dòng là tổng của ~n~ số đầu tiên trong đãy, sau khi chia dư cho ~10^9+7~.

Input:

2
3
6

Output:

5
14

Giới hạn:

• Có ~40\%~ số test ứng với ~40\%~ số điểm của bài có ~n\leq 10^6~.
• Có ~60\%~ số test còn lại ứng với ~60\%~ số điểm của bài không có ràng buộc gì thêm.