题目描述

译自 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

数据范围与提示

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