Nhà của nam0610 là nhà sản xuất gạch. Một hôm nam0610 nhận được một bức thư. Trong bức thư đó có nói rằng "ta có một ô gạch với kích thước 2x~n~ ta muốn ngươi sản xuất các viên gạch có chiều dài, chiều rộng là số nguyên dương. Ta muốn ngươi tính toán toàn bộ các trường hợp mà ngươi có thể lắp gạch được." nhưng nam0610 đã mất hàng tiếng đồng hồ để giải bài đó nhưng vẫn không có kết quả nên muốn nhờ bạn giúp

Yêu cầu: Viết ra toàn bộ trường hợp mà bạn có thể lắp gạch. Vì số quá lớn nên chia lấy dư cho ~10^9+7~

Dữ liệu vào:

• Nhập vào một số nguyên ~q~ tượng trưng cho truy vấn (~1 ≤ q ≤ 100~)
• Nhập vào một só nguyên ~n~ tượng trưng cho chiều dài của ô gạch đó(~1 ≤ n ≤ 10^6~)

Dữ liệu ra:

• Mỗi hàng viết ra toàn bộ trường hợp mà bạn có thể lắp gạch(chia lấy dư cho ~10^9+7~)

Ví dụ:

Input:

3
2
6
1337

Output:

8
2864
640403945