Một hàng 5 viên gạch vuông màu đen như hình dưới đây và có một số viên gạch được thay thế có màu được chọn từ màu đỏ (chiều dài 2), màu xanh lá cây (chiều dài 3) và màu xanh lục (chiều dài 4).

Nếu chọn gạch màu đỏ thì chúng ta có chính xác 7 cách để thực hiện việc thay thế.                                               

Nếu chọn gạch xanh lá cây thì có 3 cách để thay thế.

Và nếu chọn gạch màu xanh lục thì có 2 cách để thay thế.

Giả sử rằng màu sắc không thể trộn được và có những cách thay thế các viên gạch đen theo hàng có chiều dài 5 ( 5 ô gạch vuông màu đen) ta sẽ có: 7 + 3 + 2 = 12 (cách để thay thế).

Làm thế nào để xác định được với độ dài n (n  - là số ô vuông màu đen) ta sẽ có bao nhiêu cách để thay thế 3 loại gạch: đỏ, xanh lá và xanh lục vào n ô vuông đó, biết rằng các màu sắc không thể trộn lẫn vào nhau và ít nhất một gói màu phải được sử dụng.

Vì kết quả có thể rất lớn nên kết quả sẽ modulo cho 10⁹ + 7.

Hạn chế:

1 <= T <= 1000.

1 <= n <= 10¹⁸.

Định dạng đầu vào:

Dòng đầu tiên chưa một số nguyên T biểu thị số lượng test của bài toán.

Mỗi T dòng chưa một số nguyên n.

Định dạng đầu ra:

Đối với mỗi trường hợp thử nghiệm in ra trên từng dòng kết quả của bài toán – câu trả lời moddolu cho 10⁹ + 7.

Example:

1
5

12