配点 : $800$ 点

問題文

数直線上の $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$ はいくつあるでしょうか。

制約

• $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}$

出力

答えを整数で出力せよ。

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