AT_abc271_f [ABC271F] XOR on Grid Path

有一个 $N$ 行 $N$ 列的方格，从上往下第 $i$ 行、从左往右第 $j$ 列的格子记作 $(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, 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)$，并且可以证明其结果与顺序无关。

输入通过标准输入给出，格式如下： > $N$ > $a_{1, 1}\ a_{1, 2}\ \ldots\ a_{1, N}$ > $\vdots$ > $a_{N, 1}\ a_{N, 2}\ \ldots\ a_{N, N}$

请输出答案。

### 数据范围 - $2 \leq N \leq 20$ - $0 \leq a_{i, j} < 2^{30}\ (1 \leq i, j \leq N)$ - 输入均为整数 ### 样例解释 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)$ 由 ChatGPT 4.1 翻译