Trong toán học, tam giác Pascal là một mảng tam giác của các hệ số nhị thức. Các hàng của tam giác Pascal được liệt kê theo quy ước bắt đầu bằng hàng \(n=0\) ở trên cùng (hàng \(0\)). Các mục trong mỗi hàng được đánh số từ đầu bên trái với \(k=0\) và thường được đặt so le so với các số trong các hàng liền kề. Tam giác có thể được xây dựng theo cách sau: Trong hàng \(0\) (hàng trên cùng), có một số \(1\) duy nhất. Mỗi số của mỗi hàng tiếp theo được xây dựng bằng cách thêm số ở trên và bên trái với số ở trên và sang bên phải, coi các mục trống là \(0\) Ví dụ: số ban đầu trong hàng đầu tiên (hoặc bất kỳ số nào khác) là \(0\) và \(1\) trong khi các số \(1\) và \(3\) trong hàng thứ ba được thêm vào để tạo ra số \(4\) ở hàng thứ tư.

Ta gọi: \(P(n) = A[0,n-1]+A[1,n-2]+...+A[C(n/2)-1,n-C(n/2)]\)

Trong đó:

• \(n\) là số nhập trong input
• \(A[i,j]\) là số thứ \(i\) của hàng thứ \(j\) (Tính từ trái qua phải, số đầu tiên là số thứ 0)
• \(C(x)=\) Giá trị của \(x\) khi làm tròn lên. Ví dụ: \(C(2.5)=3\)
• \(A[i,j]=A[j,i]\)

Yêu cầu

• Nhập số \(n\). Hãy xuất \(P(n)\). Bạn phải trả lời \(t\) câu hỏi

Dữ liệu vào

• Dòng đầu nhập số \(t\) là số truy vấn \((t \le 10^5)\)
• \(t\) dòng tiếp theo, mỗi dòng là mỗi số nguyên dương \(n\) \((n \le 10^{18})\)

Dữ liệu ra

• Xuất ra \(t\) dòng, mỗi dòng là kết quả \(P(n)\) tìm được chia lấy dư cho \(10^9 + 7\)

Ràng buộc

• Subtask 1 (40% điểm): \(T \le 10^5, N \le 10^6\)
• Subtask 2 (60% điểm): \(T \le 10^5, N \le 10^{18}\)

Input 1

2
1
2

Output 1

1
1