Problem Statement

kamipeipaa, a brainy otaku, continues his studies. He never neglects to review. Today he is solving the following problem.

You have found $N$ switches. The integer $A_i$ is written on the $i$-th switch. By pressing the $i$-th switch, you can perform the following operation on an integer $X$:
$X = X \oplus A_i$
Here, $\oplus$ denotes bitwise XOR (reference).
A switch that has been pressed once can never be used again.
$X$ is initially $0$.
How many different integers can you make?

kamipeipaa noticed that he could still solve this problem even with stricter constraints, so he decided to do so. Please solve it as well.

Input

$N$
$A_1$ $A_2$ ... $A_N$

The first line contains the number of switches $N(1 \le N \le 10^{5})$.
The second line contains the integers $A_i(1 \le A_i \le 1152921504606846976(2^{60}))$ written on the switches, separated by spaces.

Output

Output the total number of integers that can be made on one line. Do not forget the newline.

Sample

2
1 2 

4

6
1 1 4 5 1 4

4

32
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 2147483648

4294967296