ami có một cái cây được định nghĩa đệ quy như sau:

1. Cây có bậc 1 chỉ chứa 1 nút
2. Cây có bậc \(i\) sẽ là cây có bậc \(i-1\) và nếu 1 nút ở cây bậc \(i-1\) có 1 nút con, gắn thêm 2 nút con vào nút này. Nếu 1 nút ở cây bậc \(i-1\) không có con, gắn thêm 1 nút con vào nút này.

Ví dụ cây có bậc 1, 2, 3:

Một móng vuốt có dạng sau:

ami có một cây bậc \(n\). Ban đầu, các nút được tô màu đen. ami có thể chọn ra một móng vuốt toàn màu đen và tô các nút trong móng vuốt thành màu hồng. Hãy tính số lượng nút tối đa được tô màu hồng trong cây này và in đáp án chia dư \(10^9+7\).

Input

• Dòng đầu tiên chứa \(t\) là số câu hỏi.
• Mỗi câu hỏi là một số nguyên dương \(n\) là cây có bậc \(n\).

Output

• Đáp án của mỗi truy vấn.

Giới hạn

• \(1 \leq n \leq 2 \cdot 10^6\)
• \(1 \leq t \leq 10^6\)

Example

1
4

4