피보나치 표현

피보나치 수열은 다음과 같이 정의한다.

• $F_1 = 1$
• $F_2 = 2$
• $n \ge 3$일 때 $F_n = F_{n-1} + F_{n-2}$

수열의 처음 몇 항은 $1, 2, 3, 5, 8, 13, 21, \ldots$이다.

양의 정수 $p$에 대해 $X(p)$는 $p$를 서로 다른 피보나치 수의 합으로 나타내는 방법의 수이다. 어떤 피보나치 수가 두 방법 중 한쪽에만 포함되면 두 방법은 다른 것으로 본다.

양의 정수 $n$개로 이루어진 수열 $a_1, a_2, \ldots, a_n$이 주어진다. 비어 있지 않은 접두부 $a_1, a_2, \ldots, a_k$마다 $p_k = F_{a_1} + F_{a_2} + \cdots + F_{a_k}$로 정의한다. $k = 1, \ldots, n$ 각각에 대해 $X(p_k)$를 $10^9 + 7$로 나눈 나머지를 구하라.

첫째 줄에 정수 $n$이 주어진다 ($1 \le n \le 100\,000$). 둘째 줄에는 공백으로 구분된 정수 $a_1, a_2, \ldots, a_n$이 주어진다 ($1 \le a_i \le 10^9$).

$n$개의 줄을 출력한다. $k$번째 줄에는 $X(p_k)$를 $10^9 + 7$로 나눈 나머지를 출력한다.