Turing hiện đang làm việc để crack các máy bí ẩn. Nhưng ông thấy rằng có hai hàm toán học là \(f(n)\) và \(g(n)\) được sử dụng để mã hóa tin nhắn của người Đức. Ông muốn thử nghiệm khám phá của mình để bắt chước cách mã hóa của máy tính.

Các hàm được định nghĩa là:

• \(g(n + 1) = 4 * g(n) + f(n + 1) + c\)
• \(f(n + 2) = 3 * f(n + 1) + 2 * f(n)\)

Dữ liệu ban đầu:

• \(f(0) = 1\);
• \(f(1) = 1\);
• \(g(-1) = 1\);
• \(g(0) = 1\);
• \(c = 2\);

Yêu cầu

• Cho số nguyên \(n\), cần phải tìm giá trị \(g(n)\) modulo \(1000000007\)

Dữ liệu vào:

• Dòng đầu tiên ghi số lượng các trường hợp thử nghiệm \(T\),
• \(T\) dòng tiếp theo mỗi dòng ghi một giá trị của \(n\).

Dữ liệu ra:

• Với mỗi test, xuất ra giá trị của \(g(n)\).

Ràng buộc

• \(1 \le T \le 1000\)
• \(1 \le n \le 10^7\)

Input 1

5
1
2
3
6
1000

Output 1

7
35
159
12835
566998663