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à \(1\) (tổng của \(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

Input

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

Output

• Xuất ra \(t\) dòng, mỗi dòng là kết quả \(P(n)\) tìm được. Vì \(P(n)\) có thể rất lớn nên hãy in ra \(P(n)\) chia lấy dư cho \(10^9+7\)

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(T = 1\), \(\dfrac{1}{2}\) số test trong số này : \(N \leq 10^6\)
• Subtask \(2\) (\(60\%\) số điểm): \(T \leq 10^5\), \(\dfrac{1}{2}\) số test trong số này : \(N \leq 10^6\)

Example

2
1
2

1
1