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

内存限制:256 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: PinkRabbit

题目描述

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