shiba là một nhân viên IT làm công ăn lương. Vì ChatGPT bùng nổ, công ty hiện shiba đang làm cắt giảm nhân sự đi, trong đó có shiba. Tuy mất việc làm nhưng để tiếp tục kiếm thêm thu nhập nuôi gia đình, shiba đã phải đi làm phụ hồ.

Ngày đầu ở cơ sở làm việc, Thầy _minhduc, một thợ chính có tiếng trong vùng, giao cho shiba một nhiệm vụ đơn giản như sau: “Đường viền trang trí ở nền nhà có kích thước \(2 \times N\) được lát bằng 2 loại gạch: loại kích thước \(1\times 2\) và loại \(2\times 2\). Hãy xác định số cách lát khác nhau có thể thực hiện. Lưu ý là với loại \(1\times 2\), ta có thể xoay nó để trở thành \(2\times 1\)”.

Thầy _minhduc muốn shiba hoàn thành nhiệm vụ trước \(14h\) ngày \(9/4\) để thầy còn tham dự contest ôn tin học trẻ bảng B của LQDOJ. Nhiệm vụ ừ thì dễ đấy, nhưng shiba chưa có kinh nghiệm bôi vôi trát vữa bao giờ. shiba liền tìm đến bạn, người anh em chí cốt của mình, để xin sự giúp đỡ. Hãy giúp shiba hoàn thành công việc đúng deadline để còn train VOI nữa chứ :Đ.

Yêu cầu: Hãy xác định số cách lát gạch có thể thực hiện, in ra kết quả sau khi chia lấy dư cho \(10^9+7\).

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) – số bộ dữ liệu \((1 \le T \le 10)\).
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(N\) \((1 \le N \le 10^{18})\), là chiều dài của nền nhà cần lát gạch vô.

Output

• In ra số cách lát gạch sau khi chia lấy dư cho \(10^9+7\).

Scoring

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

Example

3
2
8
12

3
171
2731