该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile3185.zip](file://AdditionalFile3185.zip?type=additional_file)

#3185. 「CEOI2018」斐波那契表示法

标签: 传统 | 时间限制: 4000 ms | 内存限制: 256 MiB |

题目描述

译自 CEOI2018 Day2 T1. Fibonacci Representations

译者为来自 FZYZ OI Group 的

定义斐波那契数列为：

其前几项为 $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

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

数据范围与提示