P6361 [CEOI 2018] Fibonacci representations

Translated from CEOI 2018 Day 2 T1. [Fibonacci Representations](https://ceoi2018.pl/wp-content/uploads/2018/08/fib.pdf).

We define the Fibonacci sequence as $$ \begin{aligned} F_1&=1\\ F_2&=2\\ F_n&=F_{n-1}+F_{n-2} \text{ for } n \ge 3 \end{aligned} $$ The first several terms of the sequence are $1,2,3,5,8,13,21,\ldots$. For a positive integer $p$, define $X(p)$ as the number of ways to represent $p$ as a sum of several **distinct** Fibonacci numbers. Two representations are different if and only if there exists a Fibonacci number that appears in exactly one of the two representations. Given a sequence of positive integers $a_1,a_2,\ldots,a_n$ of length $n$, for a non-empty prefix $a_1,a_2,\ldots,a_k$, we define $p_k=F_{a_1}+F_{a_2}+\cdots+F_{a_k}$. Your task is: for all $k=1,2,\ldots,n$, compute $X(p_k)$ modulo $10^9+7$.

The first line of standard input contains an integer $n$. The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ separated by spaces.

Standard output should contain $n$ lines. On the $k$-th line, output $X(p_k)$ modulo $10^9+7$.

#### Sample Explanation The values of $p_k$ are as follows: $$ \begin{aligned} p_1&=F_4=5\\ p_2&=F_4+F_1=5+1=6\\ p_3&=F_4+F_1+F_1=5+1+1=7\\ p_4&=F_4+F_1+F_1+F_5=5+1+1+8=15 \end{aligned} $$ $5$ can be represented in two ways: $F_2+F_3$ and $F_4$ alone (that is, $2+3$ and $5$), so $X(p_1)=2$. We have $X(p_2)=2$ because $p_2=1+5=2+3$. The only representation of $7$ as a sum of distinct Fibonacci numbers is $2+5$. Finally, $15$ can be represented as $2+13$ and $2+5+8$ (two representations). #### Constraints For $100\%$ of the testdata, $1\le n\le 10^5,\ 1\le a_i\le 10^9$. All testdata are divided into the following subtasks with additional restrictions. Each subtask contains several test points. | Subtask | Additional Restrictions | Points | | :--: | :---: | :--: | | $1$ | $n, a_i \leq 15$ | $5$ | | $2$ | $n, a_i \leq 100$ | $20$ | | $3$ | $n \leq 100$, and $a_i$ are distinct perfect squares | $15$ | | $4$ | $n \leq 100$ | $10$ | | $5$ | $a_i$ are distinct even numbers | $15$ | | $6$ | No additional restrictions | $35$ | Translated by ChatGPT 5