问题描述

有一个 $N$ 行 $N$ 列的方格网。我们用 $(i, j)$ 表示从上往下数的第 $i$ 行 $(1 \leq i \leq N)$、从左往右数的第 $j$ 列 $(1 \leq j \leq N)$ 的方格。
方格 $(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$ 的二进制表示中只有一个是 $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$ 的顺序无关。

约束条件

• $2 \leq N \leq 20$
• $0 \leq a_{i, j} < 2^{30} \, (1 \leq i, j \leq N)$
• 输入中的所有值都是整数。

输入

输入使用以下格式从标准输入给出：

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

输出

输出答案。

示例输入 1

3
1 5 2
7 0 5
4 2 3

示例输出 1

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

2
1 2
2 1

示例输出 2

0

示例输入 3

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

示例输出 3

24307