Let us define the sequence of Fibonacci numbers as: $$\displaystyle \begin{align} F_1 &= 1 \\ F_2 &= 2 \\ F_n &= F_{n-1} + F_{n-2} \text{ for } n \ge 3 \end{align}$$

The first few elements of the sequence are ~1, 2, 3, 5, 8, 13, 21, \dots~

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 ~a_1, a_2, \dots, a_n~. For a non-empty prefix ~a_1, a_2, \dots, a_k~, we define ~p_k = F_{a_1} + F_{a_2} + \dots + F_{a_k}~. Your task is to find the values ~X(p_k)~ modulo ~10^9 + 7~, for all ~k = 1, \dots, n~.

Input

The first line of the standard input contains an integer ~n~ ~(1 \le n \le 100\,000)~. The second line contains ~n~ space-separated integers ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^9)~.

Output

The standard output should contain ~n~ lines. In the ~k~-th line, print the value ~X(p_k)~ modulo ~(10^9 + 7)~.

Grading

The test set is divided into the following subtasks with additional constraints. Tests in each of the subtasks consist of one or more separate test groups. Each test group may contain one or more test cases.

Subtask	Constraints	Points
~1~	~n, a_i \le 15~	~5~
~2~	~n, a_i \le 100~	~20~
~3~	~n \le 100~, ~a_i~ are squares of different natural numbers	~15~
~4~	~n \le 100~	~10~
~5~	~a_i~ are different even numbers	~15~
~6~	no additional constraints	~35~

Sample Input 1

4
4 1 1 5

Sample Output 1

2
2
1
2

Explanation of Sample Output 1

~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~

The number ~5~ can be expressed in two ways: as ~F_2+F_3~ and simply as ~F_4~ (that is, ~2 + 3~ and ~5~, respectively).

Hence, ~X(p_1) = 2~.

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