Fibonacci representations

The Fibonacci sequence is defined as:

• $F_1 = 1$
• $F_2 = 2$
• $F_n = F_{n-1} + F_{n-2}$ for $n \ge 3$

The first few terms are $1, 2, 3, 5, 8, 13, 21, \ldots$

For a positive integer $p$, let $X(p)$ be the number of different ways to write $p$ as a sum of distinct Fibonacci numbers. Two ways differ if some Fibonacci number appears in exactly one of them.

You are given a sequence of $n$ positive integers $a_1, a_2, \ldots, a_n$. For each non-empty prefix $a_1, a_2, \ldots, a_k$, define $p_k = F_{a_1} + F_{a_2} + \cdots + F_{a_k}$. Find $X(p_k)$ modulo $10^9 + 7$ for every $k = 1, \ldots, n$.

The first line contains an integer $n$ ($1 \le n \le 100\,000$). The second line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$).

Print $n$ lines. The $k$-th line contains $X(p_k)$ modulo $10^9 + 7$.