Nga vừa mua được một vùng đất lớn và quyết định xây dựng thành phố của chính mình lên đó. Vùng đất được biểu diễn bằng đoạn \([0, n]\) trên trục \(Ox\) và mỗi căn nhà được biểu diễn bằng các điểm nguyên trên đoạn: \(\{x_{1}, x_{2}, \ldots, x_{k}\}\) sao cho \(x_{i} < x_>{j}\) \(\forall 1 \leq i < j \leq k\).

Nga có rất nhiều tiền và muốn xây bao nhiêu căn nhà cũng được. Nga định nghĩa một thành phố hoàn hảo là thành phố thoả mãn điều kiện:

Khoảng cách giữa mọi cặp căn nhà kề nhau phải bằng nhau. Nói cách khác, \(x_{2} - x_{1} = x_{3} - x_{2} = x_{4} - x_{3} = \ldots = x_{k} - x_{k - 1}\).

Nga thắc mắc là với một giá trị \(n\) thì sẽ có bao nhiêu cách tạo nên một thành phố hoàn hảo. Hai cách tạo thành phố được coi là khác nhau khi và chỉ khi ở một cách tạo tồn tại một căn nhà tại một điểm nguyên \(x_i\) trên trục \(Ox\) mà ở cách còn lại thì không có nhà tại điểm đó.

Input

• Dòng đầu chứa một số nguyên \(q\) (\(1 \leq q \leq 10\)) là số lượng câu hỏi cần trả lời.
• Mỗi dòng trong số \(q\) dòng tiếp theo mô tả các câu hỏi của Nga, mỗi dòng gồm duy nhất một số nguyên \(n\) (\(1 \leq n \leq 10^{12}\)) mô tả đoạn nguyên \([0, n]\) cần xây dựng thành phố hoàn hảo ở trên đó.

Output

• In ra một số nguyên tương ứng là phần dư của số cách xây thành phố hoàn hảo đối với câu hỏi tương ứng trong dữ liệu vào khi chia cho \(10^{9} + 7\).

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \leq 10^{3}\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 10^{6}\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
1
2
3
4
5

3
7
13
22
33