网格路径上的异或

题目描述

有一个 $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$ 的二进制表示的第 $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}$

输出格式

输出答案。

样例

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

数据范围

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