AT_abc390_d [ABC390D] Stone XOR

袋 $ 1 $ , 袋 $ 2 $ , $ \ldots $ , 袋 $ N $ と番号づけられた $ N $ 個の袋があります。 袋 $ i $ $ (1\leq i\leq N) $ には $ A_i $ 個の石が入っています。 高橋君は次の操作を好きなだけ（ $ 0 $ 回でも良い）繰り返すことができます。 > $ 2 $ つの袋 A, B を選び、袋 A に入っている石を **すべて** 袋 B に入れる。 操作を繰り返した後の状態における次の値としてあり得るものが何個あるか求めてください。 - 袋 $ i $ に入っている石の個数を $ B_i $ として、 $ B_1\oplus B_2\oplus\cdots\oplus B_N $ の値。 ただし、 $ \oplus $ は排他的論理和を表す。 排他的論理和とは 非負整数 $ a,b $ の排他的論理和 $ a \oplus b $ は、以下のように定義されます。 > $ a \oplus b $ を二進表記した際の $ 2^k $ $ (k \geq 0) $ の位の数は、 $ a $ , $ b $ を二進表記した際の $ 2^k $ の位の数のうち一方のみが $ 1 $ であれば $ 1 $ 、 そうでなければ $ 0 $ である。 例えば、 $ 3 \oplus 5 = 6 $ となります（二進表記すると $ 011 \oplus 101 = 110 $ ）。 一般に $ k $ 個の非負整数 $ x_1, x_2, \ldots, x_k $ の排他的論理和 $ x_1\oplus x_2\oplus\cdots\oplus x_k $ は $ (\cdots((x_1 \oplus x_2) \oplus x_3) \oplus \cdots \oplus x_k) $ と定義され、 これは $ x_1, x_2, \ldots, x_k $ の順番によらないことが証明できます。 なお、問題の制約下において、操作を繰り返した後の状態における上記の値としてあり得るものが有限個しかないことが証明できます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

高橋君が操作を繰り返した後の状態における、問題文中で定義された値としてあり得るものの個数を出力せよ。

### Sample Explanation 1 例えば、高橋君が袋 A, B として袋 $ 1 $ , $ 3 $ を選び、操作を行ったとすると、袋 $ 1,2,3 $ に入っている石はそれぞれ $ 0,5,9 $ となります。 ここで高橋君が操作を終了したとき、この状態における、袋に入っている石の個数の排他的論理和は $ 0\oplus 5\oplus 9=12 $ となります。 他に、高橋君が操作を繰り返した後の状態における、袋に入っている石の個数の排他的論理和としてあり得るものは $ 0,14 $ があります。 よって、あり得る値は $ 0,12,14 $ の $ 3 $ 個であるため、 $ 3 $ を出力します。 ### Constraints - $ 2\leq N \leq 12 $ - $ 1\leq A_i \leq 10^{17} $ - 入力はすべて整数