시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB639611.111%

문제

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 5

n, ai ≤ 15

2 20

n, ai ≤ 100

3 15

n ≤ 100, ai are squares of different natural numbers

4 10

n ≤ 100

5 15

ai are different even numbers

6 35

No additional constraints

예제 입력 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).

채점 및 기타 정보

  • 예제는 채점하지 않는다.