CEOI '18 P4 - Fibonacci Representations

View as PDF

Submit solution

Points: 40 (partial)
Time limit: 1.8s
Memory limit: 256M

Problem types

Let us define the sequence of Fibonacci numbers as: \displaystyle \begin{align}
F_1 &= 1 \\
F_2 &= 2 \\
F_n &= F_{n-1} + F_{n-2} \text{ for } n \ge 3
\end{align}

The first few elements of the sequence are 1, 2, 3, 5, 8, 13, 21, \dots

For a positive integer p, let X(p) denote the number of different ways of expressing p as a sum of different Fibonacci numbers. Two ways are considered different if there is a Fibonacci number that exists in exactly one of them.

You are given a sequence of n positive integers a_1, a_2, \dots, a_n. For a non-empty prefix a_1, a_2, \dots, a_k, we define p_k = F_{a_1} + F_{a_2} + \dots + F_{a_k}. Your task is to find the values X(p_k) modulo 10^9 + 7, for all k = 1, \dots, n.

Input

The first line of the standard input contains an integer n (1 \le n \le 100\,000). The second line contains n space-separated integers a_1, a_2, \dots, a_n (1 \le a_i \le 10^9).

Output

The standard output should contain n lines. In the k-th line, print the value X(p_k) modulo (10^9 + 7).

Grading

The test set is divided into the following subtasks with additional constraints. Tests in each of the subtasks consist of one or more separate test groups. Each test group may contain one or more test cases.

Subtask Constraints Points
1 n, a_i \le 15 5
2 n, a_i \le 100 20
3 n \le 100, a_i are squares of different natural numbers 15
4 n \le 100 10
5 a_i are different even numbers 15
6 no additional constraints 35

Sample Input 1

4
4 1 1 5

Sample Output 1

2
2
1
2

Explanation of Sample Output 1

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

The number 5 can be expressed in two ways: as F_2+F_3 and simply as F_4 (that is, 2 + 3 and 5, respectively).

Hence, X(p_1) = 2.

Then we have X(p_2) = 2 because p_2 = 1 + 5 = 1 + 2 + 3.

The only way to express 7 as a sum of different Fibonacci numbers is 2 + 5.

Finally, 15 can be expressed as 2 + 13 and 2 + 5 + 8 (two ways).


Comments

There are no comments at the moment.