問題文

数直線上の $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$ の順番によらないことが証明できます。

制約

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

入力

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

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

出力

答えを整数で出力せよ。

入力例 1

2
1 2 3

出力例 1

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

入力例 2

3
7 1 2 3 4 5 6

出力例 2

2