Fibonacci representations
시간 제한2초메모리 제한512 MB
각 접두사에 대해 대응하는 피보나치 수의 합을 구하고, 그 합을 서로 다른 피보나치 수의 합으로 나타내는 방법의 수를 10^9+7로 나눈 나머지를 출력한다.
문제
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).