问题描述

在数轴上，坐标为$x=1,2,3,...,2^N-1$的位置上有$2^N-1$个小球，第$i$个小球的重量为$w_i$。这里，$w_1, w_2,...,w_{2^N-1}$是$1$到$2^N-1$之间整数的排列。你需要选择一个不超过$2^N-1$的非负整数$Z$，并将重量$Z$附加到坐标为$x=\\pm 100^{100^{100}}$的每个位置上。然后，小球们将同时开始移动，规则如下：

• 每个时间点，假设$R$是位于小球坐标右侧的小球和附加重量的重量的异或和，$L$是位于小球坐标左侧的小球和附加重量的重量的异或和。如果$R>L$，小球向右以每秒$1$的速度移动；如果$L>R$，小球向左以每秒$1$的速度移动；如果$L=R$，小球静止不动。
• 如果有多个小球存在于同一坐标上（例如，从左边和右边来的两个小球到达同一坐标），这些小球将合并为一个小球，其重量为它们以前重量的异或和。

有多少个$Z$的值使得所有小球在$100^{100}$秒内静止不动？

什么是异或运算（$\\mathrm{XOR}$）？

非负整数$A$和$B$的二进制异或运算$A \\oplus B$定义如下：

• 当$A \\oplus B$表示为二进制形式时，第$k$位（$k \\geq 0$）是$1$当且仅当$A$和$B$的第$k$位中只有一位是$1$，否则为$0$。

例如，$3 \\oplus 5 = 6$（二进制形式为：$011 \\oplus 101 = 110$）。
通常，$k$个非负整数$p_1, p_2, p_3, \\dots, p_k$的异或运算被定义为$(\\dots ((p_1 \\oplus p_2) \\oplus p_3) \\oplus \\dots \\oplus p_k)$，并且可以证明与$p_1, p_2, p_3, \\dots, p_k$的顺序无关。

约束条件

• $2\\leq N\\leq 18$
• $1\\leq w_i\\leq 2^N-1$
• $w_i\\neq w_j$，其中$i\\neq j$。
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $w_1$ $w_2$ $\\ldots$ $w_{2^N-1}$

输出

输出一个整数作为答案。

示例一

2
1 2 3

示例一输出

1

我们将重量为$i$的小球简称为$i$。

如果$Z=0$，例如，$1$和$2$首先向右移动，$3$向左移动。然后，当$2$和$3$碰撞并合并为一个小球时，它开始向左移动。随后，当所有从$1$到$3$的小球合并为一个小球时，它静止不动。因此，$Z=0$满足条件。

另一方面，如果$Z=3$，那么$1$和$2$将继续向左移动，$3$将继续向右移动，朝着附加重量移动约$100^{100^{100}}$秒。因此，$Z=3$不满足条件。

结果表明，只有$Z=0$是满足条件的值，因此应该输出$1$。

示例二

3
7 1 2 3 4 5 6

示例二输出

2