Description

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$.

Input Format

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.

Output Format

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

4
4 1 1 5

2
2
1
2

Hint

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