题目描述

译自 CEOI2018 Day2 T1. Fibonacci Representations 译者为来自 FZYZ OI Group 的 @nealchen

定义斐波那契数列为：

$$\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$。

数据范围与提示

子任务	约束	分值
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