AT_abc271_f [ABC271F] XOR on Grid Path

[problemUrl]: https://atcoder.jp/contests/abc271/tasks/abc271_f $ N $ 行 $ N $ 列のマス目があり、上から $ i\ \,\ (1\ \leq\ i\ \leq\ N) $ 行目、左から $ j\ \,\ (1\ \leq\ j\ \leq\ N) $ 列目のマスを $ (i,\ j) $ と表します。 マス $ (i,\ j) $ には非負整数 $ a_{i,\ j} $ が書かれています。 マス $ (i,\ j) $ にいるとき、マス $ (i+1,\ j),\ (i,\ j+1) $ のいずれかに移動することができます。ただし、マス目の外に出るような移動はできません。 マス $ (1,\ 1) $ から移動を繰り返してマス $ (N,\ N) $ にたどり着く方法であって、通ったマス（マス $ (1,\ 1),\ (N,\ N) $ を含む）に書かれた整数の排他的論理和が $ 0 $ となるようなものの総数を求めてください。 排他的論理和とは 整数 $ a,\ b $ の排他的論理和 $ 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,\ \dots,\ p_k $ の排他的論理和は $ (\cdots\ ((p_1\ \oplus\ p_2)\ \oplus\ p_3)\ \oplus\ \cdots\ \oplus\ p_k) $ と定義され、これは $ p_1,\ \dots,\ p_k $ の順番によらないことが証明できます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_{1,\ 1} $ $ \ldots $ $ a_{1,\ N} $ $ \vdots $ $ a_{N,\ 1} $ $ \ldots $ $ a_{N,\ N} $

答えを出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 20 $ - $ 0\ \leq\ a_{i,\ j}\ \lt\ 2^{30}\ \,\ (1\ \leq\ i,\ j\ \leq\ N) $ - 入力は全て整数 ### Sample Explanation 1 次の二通りの方法が条件を満たします。 - $ (1,\ 1)\ \rightarrow\ (1,\ 2)\ \rightarrow\ (1,\ 3)\ \rightarrow\ (2,\ 3)\ \rightarrow\ (3,\ 3) $ - $ (1,\ 1)\ \rightarrow\ (2,\ 1)\ \rightarrow\ (2,\ 2)\ \rightarrow\ (2,\ 3)\ \rightarrow\ (3,\ 3) $