Nhà phát hành trò chơi XGAMING vừa đưa ra một trò chơi mới mang tên "Cuộc đua kì thú". Người chơi có ~T~ cánh cửa bí mật cần mở khóa, ở mỗi lượt người chơi cần tìm và nhập mật khẩu để mở khóa một cánh cửa bí mật.

Ở lượt chơi thứ ~i~, chương trình sẽ cung cấp cho người chơi một số nguyên dương ~n_i~. Mật khẩu để mở khóa cánh cửa này là số cách phân tích ~n_i~ thành tổng các lũy thừa của ~2~.

Ví dụ với ~n=6~, có đúng ~6~ cách phân tích khác nhau thỏa mãn là: (~2^0, 2^0, 2^0, 2^0, 2^0, 2^0~), (~2^0, 2^0, 2^0, 2^0, 2^1~), (~2^0, 2^0, 2^1, 2^1~), (~2^1, 2^1, 2^1~), (~2^1, 2^2~), (~2^0, 2^0, 2^2~).

Yêu cầu: Hãy tìm mật khẩu để mở khóa các cánh cửa bí mật của trò chơi.

Input

• Dòng 1: Chứa số nguyên dương ~T~ là số lượng cánh cửa bí mật cần mở khóa (~T \le 100~).

• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n_i~ mà chương trình cung cấp ở lượt chơi thứ ~i~ (~1 \le i \le T~).

Output

Gồm ~T~ dòng, dòng thứ ~i~ ghi ra giá trị ~S_i \bmod (10^9+7)~, với ~S_i~ là mật khẩu tương ứng với số nguyên dương ~n_i~ của lượt chơi thứ ~i~.

Biết rằng ~\bmod~ là phép toán chia lấy phần dư.

Scoring

Sample Input 1

5
6
5
12
8
11

Sample Output 1

6
4
20
10
14