AT_arc152_e [ARC152E] Xor Annihilation

[problemUrl]: https://atcoder.jp/contests/arc152/tasks/arc152_e 数直線上の $ 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\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 $ と答えてください。