시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 42 5 3 9.375%

문제

Let us define the sequence of Fibonacci numbers as:

  • F1 = 1
  • F2 = 2
  • Fn = Fn−1 + Fn−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 a1, a2, . . . , an. For a non-empty prefix a1, a2, . . . , ak, we define pk = Fa1 + Fa2 + . . . + Fak. Your task is to find the values X(pk) modulo 109 + 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 a1, a2, . . . , an (1 ≤ ai ≤ 109).

출력

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

예제 입력 1

4
4 1 1 5

예제 출력 1

2
2
1
2

We have the following values pk:

  • p1 = F4 = 5
  • p2 = F4 + F1 = 5 + 1 = 6
  • p3 = F4 + F1 + F1 = 5 + 1 + 1 = 7
  • p4 = F4 + F1 + F1 + F5 = 5 + 1 + 1 + 8 = 15

The number 5 can be expressed in two ways: as F2+F3 and simply as F4 (that is, 2+ 3 and 5, respectively). Hence, X(p1) = 2.

Then we have X(p2) = 2 because p2 = 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).