定义斐波那契数列如下： $$F_1 = 1$$ $$F_2 = 2$$ $$F_n = F_{n-1} + F_{n-2} \quad \text{对于 } n \ge 3$$ 该数列的前几项为 $1, 2, 3, 5, 8, 13, 21, \dots$。

对于一个正整数 $p$，令 $X(p)$ 表示将 $p$ 表示为若干个不同斐波那契数之和的方法数。如果两种表示方法中存在一个斐波那契数仅出现在其中一种表示中，则认为这两种方法是不同的。

给定一个包含 $n$ 个正整数的序列 $a_1, a_2, \dots, a_n$。对于每一个非空前缀 $a_1, a_2, \dots, a_k$，定义 $p_k = F_{a_1} + F_{a_2} + \dots + F_{a_k}$。你的任务是求出所有 $k = 1, \dots, n$ 的 $X(p_k)$ 对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 100\,000$)。第二行包含 $n$ 个空格分隔的整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)。

输出格式

标准输出应包含 $n$ 行。第 $k$ 行输出 $X(p_k)$ 对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

4
4 1 1 5

样例输出 1

2
2
1
2

说明

示例的解释：我们有以下 $p_k$ 值： $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$

数字 $5$ 可以用两种方式表示：$F_2 + F_3$ 以及 $F_4$（即 $2+3$ 和 $5$）。因此，$X(p_1) = 2$。 接着，$X(p_2) = 2$，因为 $p_2 = 1 + 5 = 1 + 2 + 3$。 将 $7$ 表示为不同斐波那契数之和的唯一方式是 $2 + 5$。 最后，$15$ 可以表示为 $2 + 13$ 和 $2 + 5 + 8$（两种方式）。

子任务

测试集分为以下具有附加约束的子任务。每个子任务中的测试由一个或多个独立的测试组组成。每个测试组可能包含一个或多个测试用例。