Hoàng Hải muốn trở thành học sinh xuất sắc của lớp chuyên Tin học nên cậu cần luyện tập nhiều bài tập lập trình. Trong quá trình học dạng số học, cậu gặp một bài toán rất hay như sau:

Một dãy số ~A~ được gọi là đặc biệt nếu thỏa mãn các điều kiện sau:

1. Giá trị tất cả các phần tử của dãy ~A~ thuộc tập hợp ~\{0, 1, \dots, n\}~, với ~n~ là số tự nhiên.

2. Dãy ~A~ gồm ít nhất ~1~ phần tử. Nếu ~A~ có từ ~2~ phần tử trở lên thì kể từ phần tử thứ ~2~, giá trị của mỗi phần tử bằng giá trị của phần tử liền trước nó cộng với một số nguyên dương không đổi ~d~.

Yêu cầu: Cho ~q~ số tự nhiên ~n~, với mỗi số ~n~ hãy đếm xem có bao nhiêu dãy số đặc biệt.

Input

• Dòng đầu chứa một số nguyên ~q~ ~(1 \le q \le 10)~ là số lượng số tự nhiên ~n~. Mỗi dòng trong số ~q~ dòng tiếp theo chứa duy nhất một số nguyên ~n~ ~(1 \le n \le 10^{12})~.

Output

• In ra ~q~ dòng, mỗi dòng một số nguyên là câu trả lời tương ứng, do kết quả có thể rất lớn nên ta lấy phần dư khi chia cho ~10^9+7~.

Scoring

Sample Input 1

6
2
4
1
5
7
8

Sample Output 1

7
22
3
33
65
86

Notes

Với ~n = 2~, ta có ~7~ dãy số đặc biệt:

• ~\{0\}~; ~\{1\}~; ~\{2\}~;

• ~\{0, 1\}~;

• ~\{0, 2\}~;

• ~\{0, 1, 2\}~;

• ~\{1, 2\}~.