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ó 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ụ: đây là một số giải pháp khả thi cho \(n = 6\):

Cho trước \(n\), hỏi bạn có thể xây được bao nhiêu tòa tháp khác nhau? Với hai tháp A,B trông khác nhau, nếu A đối xứng với B, hoặc sau khi xoay A, ta thu được tháp B, thì ta vẫn tính A và B là hai tháp riêng biệt.

Input

• Dòng đầu tiên chứa một số nguyên \(t\): số lượng test.
• \(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.

Output

• Đối với mỗi test, in số lượng tòa tháp sau khi chia lấy dư cho \(10 ^ 9 + 7\) trên một dòng riêng.

Constraints

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

Example

Sample input

3
2
6
1337

Sample output

8
2864
640403945