Cho sàn HCN gồm \(2 \times n\) ô vuông, bạn có thể lát sàn bằng các viên gạch kích cỡ \(1 \times 2\) và có thể xoay ngang dọc tuỳ ý. Hãy tính có bao nhiêu cách lát gạch khác nhau cho sàn HCN.

Input

• Dòng đầu là số nguyên \(T\) thể hiện một truy vấn \(T \le 1000\).
• \(T\) dòng tiếp theo, mỗi dòng là một số nguyên \(n\) duy nhất \((n \le 10^{18})\).

Output

• Gồm \(T\) dòng, mỗi dòng là một số nguyên duy nhất là đáp án khi lấy dư cho \(10^9 + 7\).

Example

3
1
2
5

1
2
8