说明

我们定义斐波那契数列为

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

序列的前面若干项为 $1,2,3,5,8,13,21,\ldots$。

对一个正整数 $p$，定义 $X(p)$ 为将 $p$ 用若干个不同的斐波那契数的和表示的方案数，两个方案不同当且仅当有一个斐波那契数恰好只在其中一个方案中出现。

给定一个长度为 $n$ 的正整数序列 $a_1,a_2,\ldots,a_n$，对于他的一个非空前缀 $a_1,a_2,\ldots,a_k$，我们定义 $p_k=F_{a_1}+F_{a_2}+\cdots+F_{a_k}$。

你的任务是对于所有 $k=1, 2, \ldots, n$，求出 $X(p_k)$ 对 $10^9+7$ 取模的值。

输入格式

标准输入的第一行一个整数 $n$。

第二行 $n$ 个用空格隔开的整数 $a_1,a_2,\ldots,a_n$。

输出格式

标准输出包含 $n$ 行，在第 $k$ 行输出 $X(p_k)$ 对 $10^9+7$ 取模后的值。

4
4 1 1 5

2
2
1
2

提示

样例解释

$p_k$ 的值如下：

$$\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$ 可以用两种方法表示：$F_2+F_3$ 和单独的 $F_4$（即分别为 $2+3$ 和 $5$），所以 $X(p_1)=2$。

我们有 $X(p_2)=2$ 因为 $p_2=1+5=2+3$。

将 $7$ 表示成若干不同的斐波那契数之和的唯一一种方案是 $2+5$。

最后，$15$ 可以表示成 $2+13$ 和 $2+5+8$（两种方案）。

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 10^5,\ 1\le a_i\le 10^9$。

所有测试数据被划分成以下若干个有附加限制的子任务。每个子任务中包含若干个测试点。

子任务	附加限制	分值
$1$	$n, a_i \leq 15$	$5$
$2$	$n, a_i \leq 100$	$20$
$3$	$n \leq 100$，$a_i$ 是不同的完全平方数	$15$
$4$	$n \leq 100$	$10$
$5$	$a_i$ 是不同的偶数	$15$
$6$	无附加限制	$35$