Problem Statement

The Fibonacci sequence $\{F_i\}$ is the sequence defined by $F_0 = F_1 = 1, \ F_{i+2} = F_{i+1} + F_i \ (i \geq 0)$. A number contained in the Fibonacci sequence is called a Fibonacci number.

There are $N$ fruits, and the freshness of the $i$-th fruit is $F_{A_i}$.
Here, $A_i$ is a positive integer; in particular, $A_i \neq 0$. Also, if $i \neq j$, then $A_i \neq A_j$.

Hanyu will choose at least $1$ and at most $N$ of these fruits to make mixed juice.
Since Hanyu loves Fibonacci numbers, she wants to choose the fruits so that the sum of the freshness of the chosen fruits is again a Fibonacci number.
Find the total number of such ways to choose the fruits. (It can be proved that the answer does not exceed $10^{18}$ under these constraints.)

Two ways of choosing fruits are considered different if there exists a fruit that is chosen in one but not chosen in the other.

Input

$N$
$A_1\ A_2\ \dots \ A_N$

• All inputs are integers.
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^{18}$
• If $i \neq j$, then $A_i \neq A_j$.

Output

Output the total number of ways to choose the fruits so that the sum of their freshness is a Fibonacci number.

Sample

3
3 4 5

5

4
1 10 100 1000

4

8
3 1 4 15 9 2 6 5

17