Nhiệm vụ của bạn là xây một tháp có chiều rộng là ~2~ và chiều cao là ~n~. Bạn có nguồn cung cấp không giới hạn các khối có chiều rộng và chiều cao là số nguyên.

Ví dụ, dưới đây là một số cách có thể cho ~n=6~: Cho ~n~, có bao nhiêu tháp khác nhau bạn có thể xây? Các tháp được phản chiếu và xoay được tính riêng nếu chúng trông khác nhau.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên ~t~: số lượng test.

Sau đó, có ~t~ dòng, mỗi dòng chứa một số nguyên ~n~: chiều cao của tháp.

Kết quả

Với mỗi test, in ra số lượng tháp modulo ~10^9+7~.

Giới hạn

• ~1 \le t \le 100~
• ~1 \le n \le 10^6~

Ví dụ

Dữ liệu vào:

3
2
6
1337

Kết quả:

8
2864
640403945