問題文

フィボナッチ数列 $\{F_i\}$ は、 $F_0=F_1=1,F_{i+2}=F_{i+1}+F_i(i\ge 0)$ で定義される数列です。 フィボナッチ数列に含まれる数をフィボナッチ数と言います。

$N$ 個の果物があり、 $i$ 個目の果物の新鮮さは $F_{A_i}$ です。
ここで $A_i$ は正の整数で、特に $A_i\ne 0$ です。 また、 $i\ne j$ ならば $A_i\ne A_j$ です。

はにゅさんはここから $1$ 個以上 $N$ 個以下の果物を選んでミックスジュースを作ります。
はにゅさんはフィボナッチ数が大好きなので、選んだ果物の新鮮さの総和が再びフィボナッチ数となるように果物を選びたいです。
このような果物の選び方の総数を求めてください。（解はこの制約下で ${10}^{18}$ を超えないことが証明できます。）

2つの果物の選び方が異なるとは、一方では選ばれているがもう一方では選ばれていない果物が存在することを指します。

入力

$N$
$A_1{A}_2\dots A_N$

• 入力は全て整数
• $1\le N\le 2\times {10}^5$
• $1\le A_i\le {10}^{18}$
• $i\ne j$ ならば $A_i\ne A_j$

出力

新鮮さの総和がフィボナッチ数となる果物の選び方の総数を出力してください。

サンプル

3
3 4 5

5

4
1 10 100 1000

4

8
3 1 4 15 9 2 6 5

17