题目描述

数直線上の $x=1,2,3,...,2^N-1$ の位置に $2^N-1$ 個のボールが並んでおり、$x=i$ にあるボールは $w_i$ の重みを持っています。ただし、$w_1,\ w_2,...,w_{2^N-1}$ は $1$ から $2^N-1$ までの整数を並び替えた数列です。 さらに、あなたは $2^N-1$ 以下の負でない整数 $Z$ を $1$ つ選び、座標 $x=\pm\ 100^{100^{100}}$ にそれぞれ $Z$ の重みを固定します。 その後、各ボールは次の規則にしたがって、一斉に運動を始めます。

• 各時点で、ボールの存在している座標より真に右側にある座標・ボールの重みの総 $\mathrm{XOR}$ を $R$、真に左側にある座標・ボールの重みの総 $\mathrm{XOR}$ を $L$ とすると、このボールは $R\ >\ L$ であれば右側に、$L\ >\ R$ であれば左側に毎秒 $1$ の速さで動き、$L=R$ であれば静止する。
• 左右から来たボールが同じ座標に到達したときなど、同じ座標に同時に複数のボールが存在した場合、これらのボールは合体し、その重みは合体前の重みの総 $\mathrm{XOR}$ となる。

このとき、$100^{100}$ 秒以内に全てのボールが静止するような $Z$ はいくつあるでしょうか。

$\mathrm{XOR}$ とは 非負整数 $A,\ B$ のビット単位 $\mathrm{XOR}$ 、$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$ 個の非負整数 $p_1,\ p_2,\ p_3,\ \dots,\ p_k$ のビット単位 $\mathrm{XOR}$ は $ (\dots\ ((p_1\ \oplus\ p_2)\ \oplus\ p_3)\ \oplus\ \dots\ \oplus\ p_k) $ と定義され、これは $p_1,\ p_2,\ p_3,\ \dots,\ p_k$ の順番によらないことが証明できます。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを整数で出力せよ。

题目大意

一条直线上有 $2^N-1$ 个初始坐标分别为 $1 \sim 2^N-1$ 的动点。其中坐标为 $i$ 的点有一个权值 $w_i$。

现在你要在 $+100^{100^{100}}$ 和 $-100^{100^{100}}$ 坐标处各加一个不超过 $2^N-1$ 非负权值 $Z$，然后 $2^N-1$ 个点会按照下列规则同时从初始坐标开始移动：

• 每个单位时间内，记严格小于一个点的坐标的权值异或和为 $L$，严格大于这个点的权值异或和为 $R$。当 $L < R$ 时，这个点会以 $1$ 个单位长度每个单位时间的速度向右移动；$L > R$ 时则会以同样速度向左移动；$L = R$ 时，这个点会静止不动。

• 当两个点在同一时间到达同一坐标时，这两个点会合并成一个点，新点的权值为两个点权值的异或和。

请求出可以使所有点在 $100^{100}$ 个单位时间内静止下来的 $Z$ 的个数。

（注：$+100^{100^{100}}$ 和 $-100^{100^{100}}$ 处只是增加了 $Z$ 的权值，初始时并没有动点。）

保证 $2 \le N \le 18$，$1 \le w_i \le 2^N-1$ 且 $i \not = j$ 时 $w_i \not = w_j$，输入的所有数均为整数。

何为异或和

2
1 2 3

1

3
7 1 2 3 4 5 6

2

提示

制約

• $2\leq\ N\leq\ 18$
• $1\leq\ w_i\leq\ 2^N-1$
• $i\neq\ j$ のとき $w_i\neq\ w_j$
• 入力される値はすべて整数である

Sample Explanation 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$ と答えてください。