**Lưu ý: Bản này khác bản dễ ở time limit và memory limit, ai làm được có thưởng :v **

Một dãy FIBONACCI được định nghĩa như sau: \(F_{0}\) = \(F_{1}\) = 1; \(F_{N}\) = \(F_{N-1}\) + \(F_{N-2}\) \(\forall\) \(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}}\) \(\forall\) 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