Nhà của Bi được lát gạch màu đen, mỗi viên kích thước ~1~ đơn vị. Sau thời gian dùng Bi thấy xấu quá muốn lát lại bằng gạch khác. Đại lý có bán ba loại gạch sau: Loại màu đỏ có kích thước bằng ~2~, loại màu xanh lá cây có kích thước ~3~, loại màu xanh nước biển có kích thước ~4~.

Với một chiều dài ~n = 5~ viên màu đen cũ có thể thay thế bằng các cách như hình vẽ sau:

Tổng cộng có ~12~ cách xếp nếu tổ hợp các phương án lát như trên nhà Bi sẽ rất là nhiều màu sắc.

Không sử dụng kiểu như ~1~ viên màu đỏ + ~1~ viên màu xanh lá cây lên ~5~ viên màu đen. Hỏi với độ dài ~n~ cho trước tính xem có bao nhiêu cách sắp xếp gạch như trên.

Input

Dòng thứ nhất chứa số nguyên ~T~ là số lượng testcase thỏa ~1 \le T \le 10^3~.

~T~ dòng tiếp theo mỗi dòng ghi số tự nhiên ~n~ thỏa ~1 \le n \le 10^9~.

Output

Đưa ra ~T~ dòng chứa tổng cần tìm tương ứng, do tổng quá lớn nên chia modulo cho ~10^9 + 7~

Samples

Sample Input 1

1
5

Sample Output 1

12

REF: Project Euler