配点 : $500$ 点

問題文

$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$ となるようなものの総数を求めてください。

制約

• $2 \leq N \leq 20$
• $0 \leq a_{i, j} \lt 2^{30} \, (1 \leq i, j \leq N)$
• 入力は全て整数

入力

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

$N$

$a_{1, 1}$ $\ldots$ $a_{1, N}$

$\vdots$

$a_{N, 1}$ $\ldots$ $a_{N, N}$

出力

答えを出力せよ。

3
1 5 2
7 0 5
4 2 3

2

次の二通りの方法が条件を満たします。

• $(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)$

2
1 2
2 1

0

10
1 0 1 0 0 1 0 0 0 1
0 0 0 1 0 1 0 1 1 0
1 0 0 0 1 0 1 0 0 0
0 1 0 0 0 1 1 0 0 1
0 0 1 1 0 1 1 0 1 0
1 0 0 0 1 0 0 1 1 0
1 1 1 0 0 0 1 1 0 0
0 1 1 0 0 1 1 0 1 0
1 0 1 1 0 0 0 0 0 0
1 0 1 1 0 0 1 1 1 0

24307