题目描述

译自 CEOI2018 Day2 T1. Fibonacci Representations

译者为来自 FZYZ OI Group 的

定义斐波那契数列为：

$$\begin{align}F_1&=1\\F_2&=2\\F_n&=F_{n-1}+F_{n-2},&n \geq 3\end{align}$$

其前几项为 $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)\bmod(10^9+7)$。

输入格式

第一行一个整数 $n\ (1 \leq n \leq 100\,000)$。

第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n\ (1 \leq a_i \leq 10^9)$。

输出格式

$n$ 行，第 $k$ 行为 $X(p_k)\bmod(10^9+7)$。

样例

4
4 1 1 5

2
2
1
2

$$\begin{align}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{align}$$

$5$ 有两种表示法：$F_2+F_3=2+3$ 和 $F_4=5.$ 因此 $X(p_1)=2$；

$6$ 有两种表示法：$1+5=1+2+3$；

$7$ 只有一种表示法：$2+5$；

$15$ 有两种表示法：$2+13=2+5+8$。

数据范围与提示