nqson đang sống ở một thế giới có vô hạn thành phố, được đánh số thứ tự từ 1 đến vô cùng. Giao thông ở đây rất đặc biệt: Từ bất kỳ thành phố ~x~ nào, bạn luôn đứng trước 2 con đường (Trái và Phải), mỗi con đường lại chia thành 2 nhánh nhỏ. Tổng cộng từ thành phố ~x~ sẽ có 4 vé thông hành dẫn đến các đích sau:

• Nếu chọn đường bên Trái:

  • Đi nhánh trái: Dẫn tới thành phố ~x \times 2 - 1~
  • Đi nhánh phải: Dẫn tới thành phố ~x \times 2~

• Nếu chọn đường bên Phải:

  • Đi nhánh trái: Dẫn tới thành phố ~x \times 2~
  • Đi nhánh phải: Dẫn tới thành phố ~x \times 2 + 1~

Mỗi nhánh đường con chỉ được đi qua tối đa 1 lần duy nhất. Do hầu hết các nhánh đều dẫn ta tiến về các thành phố có số lớn hơn, ngoại trừ ở thành phố 1: nhánh Trái - trái sẽ dẫn ngược về chính nó (~1 \times 2 - 1 = 1~). Vì vậy sẽ có đúng 2 cách để bắt đầu:

1. Đứng yên không di chuyển (tốn 0 bước).
2. Dạo một vòng qua nhánh Trái - trái để trở về lại thành phố 1 (lúc này nhánh này sẽ bị khóa và không thể đi tiếp vòng nữa).

Có ~t~ ngày, mỗi ngày mới bắt đầu, nqson sẽ được hệ thống đưa trở lại thành phố 1. Bạn hãy giúp nqson mỗi ngày tính xem có tất cả bao nhiêu cách khác nhau để di chuyển từ thành phố 1 đến thành phố ~n~.

Lưu ý: Vì kết quả có thể rất lớn, hãy in ra phần dư của số cách tìm được khi chia cho ~10^9+7~.

Đầu vào

Dòng đầu tiên ~t~ là số ngày

~t~ dòng tiếp theo, mỗi dòng chứa số nguyên dương ~n~ - đại diện cho thành phố đích mà nqson muốn tới.

Đầu ra

~t~ dòng, mỗi dòng in ra một số nguyên duy nhất là số cách di chuyển từ thành phố 1 tới thành phố ~n~ vào ngày đó (sau khi đã modulo cho ~10^9+7~).

Giới hạn

• Subtask 1 (25% số điểm): ~t = 1, 1 \le n \le 10^3~.
• Subtask 2 (25% số điểm): ~t = 1, 1 \le n \le 10^6~.
• Subtask 3 (25% số điểm): ~t \le 10^5, 1 \le n \le 10^7~.
• Subtask 4 (25% số điểm): ~t \le 10^6, 1 \le n \le 10^{18}~.

Ví dụ 1

Đầu vào

2
2
1

Đầu ra

4
2

Giải thích

Có 4 cách khác nhau để đi từ thành phố 1 tới thành phố 2:
- Cách 1: Từ 1 --> rẽ nhánh (Trái - phải) --> đến 2.
- Cách 2: Từ 1 --> rẽ nhánh (Phải - trái) --> đến 2.
- Cách 3: Từ 1 --> rẽ nhánh (Trái - trái) vòng lại 1 --> rẽ nhánh (Trái - phải) --> đến 2.
- Cách 4: Từ 1 --> rẽ nhánh (Trái - trái) vòng lại 1 --> rẽ nhánh (Phải - trái) --> đến 2.

Có đúng 2 trạng thái xuất phát hợp lệ tại thành phố 1:
- Cách 1: Không làm gì cả (đứng yên tại chỗ).
- Cách 2: 1 --> rẽ nhánh (Trái - trái) --> 1. Nhánh này lúc này đã bị khóa nên không thể đi tiếp vòng 2.