Với định nghĩa dãy ~fibo~ như sau ~f_0 = 0, f_1 = 1~ với ~i > 1~ và ~f_i = f_{i-1} + f_{i-2}~. Bạn hãy trả lời ~m~ câu hỏi sau mỗi câu hỏi đưa số nguyên dương ~n~ hãy tính số ~fibo~ thứ ~n~ hay chính là ~f_n~. Vì kết quả có thể rất lớn nên in ra ~f_n~ mod ~1e9+7~

Input

Dòng đầu tiên là số nguyên dương ~m~ ~(1 \le m \le 1000000)~ số lượng câu hỏi

Gồm ~m~ dòng chứa ~1~ số nguyên dương ~n~ ~(1 \le n \le 1000000)~.

Output

Ghi ra ~m~ dòng mỗi dòng là giá trị ~f_n~ mod ~1e9+7~.

Sample Input

3
2
3
4

Sample Output

1
2
3

Subtask

• ~50\%~ số test có ~n,m \le 1000~
• ~50\%~ số test còn lại không có điều kiện gì thêm

Note

Gợi ý: Sử dụng toán tử "+".