16029번 - Fibonacci representations 서브태스크다국어

문제

Let us define the sequence of Fibonacci numbers as:

• F₁ = 1
• F₂ = 2
• F_n = F_n−1 + F_n−2 for n ≥ 3

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

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₁, a₂, . . . , a_n. For a non-empty prefix a₁, a₂, . . . , a_k, we define p_k = F_a1 + F_a2 + . . . + F_ak. Your task is to find the values X(p_k) modulo 10⁹ + 7, for all k = 1, . . . , n.

입력

The first line of the standard input contains an integer n (1 ≤ n ≤ 100 000). The second line contains n space-separated integers a₁, a₂, . . . , a_n (1 ≤ a_i ≤ 10⁹).

출력

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

제한

서브태스크

힌트