Đếm Tháp

Xây một tháp có chiều rộng $2$ và chiều cao $n$ bằng các khối gạch hình chữ nhật có kích thước nguyên. Hãy đếm số cách xây tháp khác nhau về cấu trúc.

In ra kết quả theo modulo ${10}^9+7$.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $t$: số truy vấn.

• $t$ dòng tiếp theo, mỗi dòng chứa một số nguyên $n$.

Dữ liệu ra

Với mỗi truy vấn, in ra số cách xây tháp, modulo ${10}^9+7$.

Ràng buộc

• $1\le t\le 100$
• $1\le n\le {10}^6$

Ví dụ