Sau cơn mưa rào cuối chiều, những giọt nước còn sót lại trên tán lá bắt đầu rơi lách tách xuống sân trường, làm nổi bật mùi đất ẩm nồng nàn và tiếng ve ngân nga xa xăm. Nắng nhẹ cuối ngày xuyên qua những tán bàng già, đổ những vệt bóng dài loang lổ lên con đường lát gạch vuông vức dẫn từ dãy hành lang cũ về phía cổng chính. SIN thong thả dạo bước, đôi mắt lơ đãng nhìn xuống chân. Nhìn những món quà của thiên nhiên rơi rụng sau cơn mưa, SIN nảy ra ý định thực hiện một trò chơi sắp đặt nhỏ để lưu giữ khoảnh khắc này. Vì bản tính có phần lười biếng và thích sự tối giản, SIN chỉ muốn tác phẩm của mình gói gọn trên một đoạn đường có kích thước đúng ~1 \times N~ (gồm ~N~ viên gạch nối tiếp nhau thành một hàng duy nhất).

SIN đứng đó, lặng lẽ quan sát từng món đồ vật nằm rải rác. Để lấp đầy khít đoạn đường này mà không để hở bất kỳ khoảng trống nào, cũng không cho phép các vật phẩm chồng lấn hay chìa ra ngoài, SIN đặt ra các quy tắc về kích thước và chủng loại vật phẩm cực kỳ khắt khe:

• Lá Bàng: Mỗi chiếc lá có kích thước vừa vặn ~1 \times 1~ (chiếm đúng ~1~ viên gạch). Tại mỗi vị trí đặt lá, SIN có đúng ~2~ sự lựa chọn về trạng thái cảm xúc: hoặc là sắc xanh mướt của sự sống, hoặc là sắc đỏ úa của thời gian.

• Cành Cây Khô: Những cành cây khẳng khiu này có kích thước dài hơn là ~1 \times 2~ (chiếm dụng vừa khít ~2~ viên gạch liên tiếp). SIN quy định mỗi khi sử dụng vật phẩm này, cậu phải chọn ~1~ trong ~3~ kiểu dáng khác nhau: thẳng tắp, uốn cong hoặc có nhánh phụ để hàng gạch không đơn điệu.

• Quả Bàng: Đây là vật phẩm lớn nhất với kích thước ~1 \times 3~ (chiếm trọn một dãy ~3~ viên gạch nối tiếp). Vì các quả bàng đều đồng nhất về hình dạng, SIN chỉ có duy nhất ~1~ cách đặt (~1~ chủng loại) cho vật phẩm này.

SIN mơ màng đứng trước những đoạn đường có độ dài khác nhau: "Liệu có bao nhiêu cách để mình lấp đầy những tác phẩm này đây?". Biết rằng hai cách sắp xếp được coi là khác nhau nếu tồn tại ít nhất một vị trí viên gạch được lấp bởi loại vật phẩm khác nhau hoặc kiểu dáng khác nhau về mặt cảm quan. Vì con số này có thể rất lớn, SIN chỉ cần bạn tính kết quả theo modulo ~10^9+7~.

Input

• Dòng đầu tiên chứa số nguyên ~T~ ~(1 \le T \le 10^4)~ - số lượng bộ thử.

• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên duy nhất ~N~ ~(1 \le N \le 10^{18})~.

Output

Gồm ~T~ dòng, mỗi dòng là một số nguyên duy nhất là số cách tìm được tương ứng với mỗi ~N~ (modulo ~10^9+7~).

Scoring

Sample Input 1

3
1
2
3

Sample Output 1

2
7
21