Đếm Tháp

Trong một buổi phỏng vấn tuyển dụng, FullHouse Dev đã đưa ra một bài toán thú vị cho các ứng viên. Họ được yêu cầu tính toán số cách xây dựng một tòa tháp đặc biệt.

Bài toán

FullHouse Dev yêu cầu xây dựng một tòa tháp có chiều rộng là 2 và chiều cao là \(n\). Bạn có vô hạn các khối gạch với chiều rộng và chiều cao là các số nguyên. Nhiệm vụ của bạn là đếm số cách xây dựng tháp khác nhau. Các tháp được xem là khác nhau nếu chúng nhìn khác nhau khi được lật hoặc xoay.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(t\) - số lượng test case
• \(t\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(n\) - chiều cao của tháp cần xây

OUTPUT FORMAT:

• Với mỗi test case, in ra số cách xây tháp theo modulo \(10^9+7\)

Ràng buộc:

• \(1 \leq t \leq 100\)
• \(1 \leq n \leq 10^6\)

Ví dụ

INPUT

3
2
6
1337

OUTPUT

8
2864
640403945

Giải thích

• Với \(n = 2\), có 8 cách xây tháp khác nhau
• Với \(n = 6\), có 2864 cách xây tháp khác nhau
• Với \(n = 1337\), có 640403945 cách xây tháp (sau khi lấy modulo \(10^9+7\))