Lưu ý: Bản này khác bản dễ ở time limit và memory limit

Một dãy FIBONACCI được định nghĩa như sau: \(F_0 = F_1 = 1\); \(F_N = F_{N-1} + F_{N-2}\) \(∀\) \(N > 1\).

Một vài phần tử đầu của dãy là: 1,1,2,3,5,8,13,21,...

Với mỗi số nguyên dương \(p\), gọi \(D_p\) là số cách biểu diễn số \(p\) dưới dạng tổng các số FIBONACCI khác nhau.

Bạn được cho một mảng \(A\) gồm \(N\) phần tử. Với mỗi giá trị \(k\) = \(1, 2, ..., N\), ta định nghĩa \(p_k\) = \(F_{A_1} + F_{A_2} + ... + F_{A_k}\). Nhiệm vụ của bạn là hãy tính \(D_{p_k}\) \(∀\) \(k\) = \(1, 2, ... , N\). Vì kết quả rất lớn nên đáp án cuối cùng là \(D_{p_k}\) modulo \(10^9+7\).

Input

• Dòng thứ nhất là số nguyên dương \(N\), số phần tử của mảng \(A\).
• Dòng thứ hai gồm các số nguyên dương \(A_1, A_2, ... , A_N\).

Output

Gồm \(N\) dòng, mỗi dòng là \(D_{p_k}\) modulo \(10^9+7\).

Scoring

• Subtask \(1\) (\(5\%\) số điểm): \(N, A_i \leq 15\).
• Subtask \(2\) (\(20\%\) số điểm): \(N, A_i \leq 100\).
• Subtask \(3\) (\(15\%\) số điểm): \(N \leq 100\), \(A_i\) là số chính phương.
• Subtask \(4\) (\(10\%\) số điểm): \(N \leq 100\), \(A_i\) không có giới hạn gì thêm.
• Subtask \(5\) (\(15\%\) số điểm): \(A_i\) là các số chẵn.
• Subtask \(6\) (\(35\%\) số điểm): \(N \leq 10^5, A_i \leq 10^9\)

Example

4
4 1 1 5 

2
2
1
2