Dãy Fibonacci trong bài này được định nghĩa như sau:

• \(F_1=1\).
• \(F_2=2\).
• \(F_n=F_{n-1}+F_{n-2}\) với \(n\ge3\).

Các số đầu tiên là \(1,2,3,5,8,13,21,\ldots\). Với số nguyên dương \(p\), gọi \(X(p)\) là số cách biểu diễn \(p\) thành tổng của các số Fibonacci khác nhau. Hai cách biểu diễn được xem là khác nhau nếu tồn tại một số Fibonacci xuất hiện trong đúng một cách.

Cho dãy số nguyên dương \(a_1,a_2,\ldots,a_n\). Với mỗi tiền tố không rỗng \(a_1,a_2,\ldots,a_k\), đặt \(p_k=F_{a_1}+F_{a_2}+\cdots+F_{a_k}\). Hãy tính \(X(p_k)\) modulo \(10^9+7\) với mọi \(k=1,2,\ldots,n\).

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\) (\(1\le n\le100000\)).

Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\) (\(1\le a_i\le10^9\)).

Dữ liệu ra

In \(n\) dòng. Dòng thứ \(k\) chứa \(X(p_k)\) modulo \(10^9+7\).

Ví dụ

4
4 1 1 5

2
2
1
2

Giải thích

Các giá trị lần lượt là \(p_1=F_4=5\), \(p_2=F_4+F_1=6\), \(p_3=F_4+F_1+F_1=7\) và \(p_4=F_4+F_1+F_1+F_5=15\).

Số \(5\) có hai cách biểu diễn: \(F_2+F_3\) và \(F_4\). Số \(6\) có hai cách: \(F_1+F_4\) và \(F_1+F_2+F_3\). Số \(7\) chỉ có cách \(F_2+F_4\). Số \(15\) có hai cách: \(F_2+F_6\) và \(F_2+F_4+F_5\).

Phân nhóm

1. \(5\) điểm: \(n,a_i\le15\).
2. \(20\) điểm: \(n,a_i\le100\).
3. \(15\) điểm: \(n\le100\) và các \(a_i\) là các số chính phương đôi một khác nhau.
4. \(10\) điểm: \(n\le100\).
5. \(15\) điểm: Các \(a_i\) là các số chẵn đôi một khác nhau.
6. \(35\) điểm: Không có ràng buộc bổ sung.