说明

时间限制：1 Sec 内存限制：256 MB 输入文件：int.in 输出文件：int.out

你有一个整数 $X$，初始值是 $0$。你还有 $N$ 个正整数 $A_1,A_2,...,A_N$。你可以选择其中的 $K$ 个 $A_{i_1},A_{i_2},...,A_{i_K}$，将 $X$ 变成 $X \oplus A_{i_1} \oplus A_{i_2} \oplus ... \oplus A_{i_K}$。你也可以一个也不选，这样 $X$ 就保持不变。

其中，$\oplus$ 是二进制异或操作，即 XOR。

你想知道可以变出多少个不同的非负整数。

输入格式

第一行一个正整数 $N$。

第二行 $N$ 个正整数 $A_1,A_2,...,A_N$。

输出格式

一个整数，表示可以变出多少个不同的非负整数。

样例

样例 1

2
1 2

4

样例说明：

$0=0$

$1=0 \oplus 1$

$2=0 \oplus 2$

$3=0 \oplus 1 \oplus 2$

样例 2

6
1 1 4 5 1 4

4

样例 3

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

数据范围

对于 24% 的数据，$N \le 100$，$A_i \le 2^{20}$。

对于 40% 的数据，$N \le 100$。

对于 100% 的数据，$1 \le N \le 10^5$，$1 \le A_i \le 1152921504606846976(2^{60})$。