Công nghệ ngày càng phát triển nên con người đã quen thuộc với máy tính, hệ nhị phân từ đó trở nên gần gũi với con người không khác gì hệ thập phân. Để đạt được sự tiện ích và đồng bộ giữa máy móc và con người, các chuyên gia Tin học đã cố vấn cho Chính phủ loại bỏ hệ thập phân và thay bằng hệ nhị phân. Với sự thay đổi này, mọi ngành nghề, lĩnh vực đều chịu ảnh hưởng.

Ngân hàng SBANK đã thu hồi tất cả những tờ tiền có mệnh giá ~1000,2000,5000,10000,…~ đồng trước đây. Thay vào đó, tất cả tờ tiền có mệnh giá là lũy thừa của ~2~ như ~1,2,…,~ ~2^k~,… đồng được phát hành. Quân là một nhân viên của ngân hàng quản lí tài khoản tiền gửi của ~T~ khách hàng, khách hàng thứ ~i~ cần rút số tiền gửi là ~n_i~. Quân muốn biết với mỗi khách hàng đến rút tiền có bao nhiêu cách trả tiền khác nhau nếu sử dụng hệ thống các tờ tiền mệnh giá mới. Hai cách đổi được xem là khác nhau nếu tồn tại một mệnh giá mà số lần xuất hiện của tờ tiền có mệnh giá này trong cách trả tiền thứ nhất khác với cách trả tiền thứ hai.

Ví dụ: Với ~n=5~ ta có

Cách trả tiền ~5=1+2+1+1~ khác với cách trả tiền ~5=4+1~ vì tờ tiền có mệnh giá 4 có số lần xuất hiện trong hai cách trả tiền là khác nhau (~0~ lần và ~1~ lần);

Cách trả tiền ~5=1+2+1+1~ giống với cách trả tiền ~5=2+1+1+1~ vì số lần xuất hiện của các mệnh giá (1 và 2) trong cách đều giống nhau (3 lần và 1 lần).

Yêu cầu: Hãy giúp Quân tính số cách trả tiền khác nhau cho mỗi khách hàng.

Dữ liệu:

• Dòng đầu tiên chứa số nguyên dương ~T~ ~(T≤100)~ là số lượng tài khoản của các khách hàng;
• Mỗi dòng trong số ~T~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên dương ~n_i~ là số tiền cần rút của khách hàng thứ ~i~.

Kết quả: Ghi ra T dòng, dòng thứ ~i~ ghi ra ~C_i~ mod ~10^9~+~7~, với ~C_i~ là số cách trả tiền tương ứng ~n_i~ đồng trong dữ liệu vào.

Ràng buộc:

• Số test ứng với 20% số điểm của bài có: ~n_i~≤~100~;
• Số test khác ứng với 30% số điểm của bài có: ~n_i~≤ ~10^5~;
• Số test khác ứng với 30% số điểm của bài có: ~n_i~≤~10^7~;
• Số test còn lại ứng với 20% số điểm của bài có: ~n_i~≤~10^{18}~.

Ví dụ:

INPUT

2
2
6

OUTPUT

2
6

Giải thích:

• Với ~n_1~=~2~, có ~2~ cách đổi tiền là: ~{2} và {1+1}~.
• Với ~n_2~=~6~, có ~6~ cách đổi tiền là ~{4+2}, {4+1+1}, {2+2+2}, {2+2+1+1}, {2+1+1+1+1} và {1+1+1+1+1+1}.~