Bài toán: Đếm số cách xây tháp

Đề bài

Bạn cần 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ó số lượng vô hạn các khối có chiều rộng và chiều cao nguyên để xây dựng.

Tòa tháp có thể bao gồm các khối được sắp xếp theo nhiều cách khác nhau. Lưu ý: các tòa tháp đối xứng hoặc xoay không được tính là giống nhau nếu chúng nhìn khác nhau.

Input

• Dòng đầu tiên chứa một số nguyên ~ t ~: số lượng bài kiểm tra.
• ~ t ~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~ n ~: chiều cao của tòa tháp.

Output

• Với mỗi bài kiểm tra, in ra số lượng tòa tháp có thể xây dựng 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 chiều cao ~ n = 2 ~, có 8 cách xây dựng tòa tháp.
• Với chiều cao ~ n = 6 ~, có 2864 cách.
• Với ~ n = 1337 ~, kết quả là 640403945 (lấy modulo ~ 10^9 + 7 ~).