Lưu ý: bài này chỉ khác CSES - Counting Towers | Đếm tháp ở giới hạn \(t\) và \(n\).

Nhiệm vụ của bạn là 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ô số các khối có chiều rộng và chiều cao là số nguyên.

Ví dụ: đây là một số cách xây dựng với \(n = 6\):

Cho trước số \(n\), bạn có thể xây dựng bao nhiêu tòa tháp khác nhau? Các tháp được tính là riêng biệt nếu chúng trông khác nhau.

Input

• Dòng đầu tiên chứa một số nguyên \(t\): số lượng test.
• Sau đó, có \(t\) dòng và mỗi dòng chứa một số nguyên \(n\): chiều cao của tháp.

Output

• Ứng với mỗi test, in ra số lượng tòa tháp có thể xây được sau khi chia lấy dư cho \(10^9 + 7\).

Constraints

• \(1 \le t \le 10^4\)
• \(1 \le n \le 10^{18}\)

Example

3
2
6
1337

8
2864
640403945