Score : $500$ points

Problem Statement

There is a grid with $N$ rows and $N$ columns. We denote by $(i, j)$ the square at the $i$-th $(1 \leq i \leq N)$ row from the top and $j$-th $(1 \leq j \leq N)$ column from the left. Square $(i, j)$ has a non-negative integer $a_{i, j}$ written on it.

When you are at square $(i, j)$, you can move to either square $(i+1, j)$ or $(i, j+1)$. Here, you are not allowed to go outside the grid.

Find the number of ways to travel from square $(1, 1)$ to square $(N, N)$ such that the exclusive logical sum of the integers written on the squares visited (including $(1, 1)$ and $(N, N)$) is $0$.

Constraints

• $2 \leq N \leq 20$
• $0 \leq a_{i, j} \lt 2^{30} \, (1 \leq i, j \leq N)$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$

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

$\vdots$

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

Output

Print the answer.

3
1 5 2
7 0 5
4 2 3

2

The following two ways satisfy the condition:

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