Bụi cây gốc

Ta định nghĩa Bụi cây gốc (RDB) cấp $n$ là một cây có gốc được xây dựng như sau:

• RDB cấp $1$ là một đỉnh duy nhất.
• Để dựng RDB cấp $i$, trước hết dựng RDB cấp $i-1$, sau đó với mỗi đỉnh $u$:
  • nếu $u$ chưa có con nào thì thêm cho $u$ đúng một con;
  • nếu $u$ có đúng một con thì thêm cho $u$ hai con (thành ba con);
  • nếu $u$ có nhiều hơn một con thì bỏ qua $u$.

Một cái vuốt (claw) là một cây gốc gồm bốn đỉnh: một đỉnh gốc (gọi là tâm) và ba con của nó.

Ban đầu mọi đỉnh của RDB đều màu xanh. Trong một nước đi, ta chọn một cái vuốt nằm trong cây sao cho cả bốn đỉnh của nó đều còn xanh và cả ba đỉnh còn lại đều là con trực tiếp của tâm, rồi tô cả bốn đỉnh đó thành màu vàng.

Cho RDB cấp $n$. Hãy tìm số đỉnh màu vàng lớn nhất có thể đạt được. Vì đáp số có thể rất lớn, in ra kết quả theo modulo ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $t$: số lượng truy vấn.
• $t$ dòng tiếp theo, mỗi dòng chứa một số nguyên $n$: cấp của RDB trong truy vấn tương ứng.

Dữ liệu ra

• Với mỗi truy vấn, in ra trên một dòng số đỉnh vàng lớn nhất theo modulo ${10}^9+7$.

Ràng buộc

• $1\le t\le {10}^4$
• $1\le n\le 2·{10}^6$

Ví dụ