Definamos la secuencia de los números de Fibonacci como:

~F_1 = 1~

~F_2 = 2~

~F_n = F_{n - 1} + F_{n - 2}~ para ~n \ge 3~

Los primeros elementos de la secuencia son 1, 2, 3, 5, 8, 13, 21,. . .

Para un entero positivo ~p~, sea ~X(p)~ el número de formas diferentes de expresar ~p~ como una suma de diferentes Números de Fibonacci. Dos formas se consideran diferentes si hay un número de Fibonacci que existe exactamente en una de ellos.

Se le da una secuencia de ~n~ enteros positivos ~a_1, a_2,... , a_n~. Para un prefijo no vacío ~a_1, a_2,... , a_k~, nosotros definimos a ~p_k = F_{a_1} + F_{a_2} +... + F_{a_k}~.

Tarea

Su tarea es encontrar los valores ~X(_{p_k})~ módulo ~10^9 + 7~, para todo ~k = 1,... , n~.

Entrada

La primera línea de la entrada estándar contiene un entero ~n~ ~(1 \le n \le 100 000)~. La segunda linea contiene ~n~ enteros separados por espacios ~a_1, a_2,... , a_n~ ~(1 \le a_i \le 10^9)~.

Salida

La salida estándar debe contener ~n~ líneas. En la ~k-th~ línea, imprima el valor ~X(_{p_k})~ módulo ~(10^9 + 7)~.

Ejemplo de Entrada

4
4 1 1 5

Ejemplo de Salida

2
2
1
2

Explicación del ejemplo:

Tenemos los siguientes valores ~p_k~:

~p_1 = F_4 = 5~

~p_2 = F_4 + F_1 = 5 + 1 = 6~

~p_3 = F_4 + F_1 + F_1 = 5 + 1 + 1 = 7~

~p_4 = F_4 + F_1 + F_1 + F_5 = 5 + 1 + 1 + 8 = 15~

El número ~5~ se puede expresar de dos maneras: como ~F_2~ + ~F_3~ y simplemente como ~F_4~ (es decir, ~2 + 3~ y ~5~, respectivamente).

Por lo tanto, ~X(_{p_1}) = 2~.

Entonces tenemos ~X(p_2) = 2~ porque ~p_2 = 1 + 5 = 1 + 2 + 3~.

La única manera de expresar 7 como una suma de diferentes números de Fibonacci es ~2 + 5~.

Finalmente, 15 se puede expresar como ~2 + 13~ y ~2 + 5 + 8~ (dos formas).

Calificación

El conjunto de prueba se divide en las siguientes subtareas con restricciones dicionales. Cada una de las subtareas consisten en uno o más grupos de prueba separados. Cada grupo de prueba puede contener uno o más casos de prueba.

Subtarea Restricciones y Puntos

~1~ ~ ~ ~ ~n~,~ ~a_i \le 15~ ~ ~ ~ ~ 5 Puntos

~2~ ~ ~ ~ ~n~,~ ~a_i \le 100~ ~ ~ ~ ~ 20 Puntos

~3~ ~ ~ ~ ~n ≤ 100~,~ ~a_i~ ~ ~ ~ ~son cuadrados de diferentes números naturales ~ ~ ~ ~ ~ ~ 15 Puntos

~4~ ~ ~ ~ ~n ≤ 100~ ~ ~ ~ ~ ~ 10 Puntos

~5~ ~ ~ ~ ~ a_i~ ~ ~ ~ ~ ~ son números pares diferentes ~ ~ ~ ~ ~ ~ 15 Puntos

~6~ ~ ~ ~ ~ sin restricciones adicionales ~ ~ ~ ~ ~ ~ 35 Puntos