Fibonacci Sum Representations

We define the Fibonacci sequence as follows:

\[ \begin{aligned} F_1 &= 1,\\ F_2 &= 2,\\ F_n &= F_{n-1} + F_{n-2} \quad \text{for } n \ge 3, \end{aligned} \]

The first few terms of the sequence are \(1, 2, 3, 5, 8, 13, 21, \ldots\).

For any positive integer \(p\), let \(X(p)\) denote the number of ways to represent \(p\) as a sum of several distinct Fibonacci numbers. Two representations are considered different if there is a Fibonacci number that appears in exactly one representation.

Given a sequence of positive integers \(a_1, a_2, \ldots, a_n\), define for each nonempty prefix \(a_1, a_2, \ldots, a_k\) the number \[ p_k = F_{a_1} + F_{a_2} + \cdots + F_{a_k}. \] Your task is to compute \(X(p_k) \bmod (10^9+7)\) for all \(k=1,2,\ldots,n\).

Note: Since every positive integer can be represented as a sum of distinct Fibonacci numbers (by choosing only those Fibonacci numbers which do not exceed the number), the count \(X(p)\) is equivalent to counting the number of subsets of the set
\(\{F_i: F_i \le p\}\) that sum to \(p\) (each Fibonacci number can be used at most once).

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 10^5\)) representing the length of the sequence.

The second line contains \(n\) space-separated positive integers \(a_1, a_2, \ldots, a_n\) (we guarantee \(1 \le a_i \le 30\)).

outputFormat

Output \(n\) lines. The \(k\)-th line should contain the value of \(X(p_k) \bmod (10^9+7)\) for the prefix \(a_1, a_2, \ldots, a_k\).

sample

3
1 2 3

1
2
2