CF1006F.Xor-Paths

There is a rectangular grid of size $n \times m$. Each cell has a number written on it; the number on the cell ($i, j$) is $a_{i, j}$. Your task is to calculate the number of paths from the upper-left cell ($1, 1$) to the bottom-right cell ($n, m$) meeting the following constraints:

• You can move to the right or to the bottom only. Formally, from the cell ($i, j$) you may move to the cell ($i, j + 1$) or to the cell ($i + 1, j$). The target cell can't be outside of the grid.
• The xor of all the numbers on the path from the cell ($1, 1$) to the cell ($n, m$) must be equal to $k$ (xor operation is the bitwise exclusive OR, it is represented as '^' in Java or C++ and "xor" in Pascal).

Find the number of such paths in the given grid.

有一个大小为 $n \times m$ 的矩形网格。每个格子中写有一个数字；格子 $(i, j)$ 中的数字为 $a_{i, j}$。你的任务是计算从左上角格子 $(1, 1)$ 到右下角格子 $(n, m)$ 的路径数量，要求满足以下约束条件：

• 每次只能向右或向下移动。形式化地说，从格子 $(i, j)$ 出发，你只能移动到格子 $(i, j + 1)$ 或格子 $(i + 1, j)$。目标格子不能超出网格边界。
• 从格子 $(1, 1)$ 到格子 $(n, m)$ 的路径上所有数字的异或（xor）结果必须等于 $k$（异或运算是按位异或，在 Java 或 C++ 中表示为 ^，在 Pascal 中表示为 xor）。

请找出给定网格中满足上述条件的路径数量。

The first line of the input contains three integers $n$, $m$ and $k$ ($1 \le n, m \le 20$, $0 \le k \le 10^{18}$) — the height and the width of the grid, and the number $k$.

The next $n$ lines contain $m$ integers each, the $j$-th element in the $i$-th line is $a_{i, j}$ ($0 \le a_{i, j} \le 10^{18}$).

输入的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n, m \le 20$，$0 \le k \le 10^{18}$）—— 分别表示网格的高度、宽度以及数字 $k$。

接下来的 $n$ 行，每行包含 $m$ 个整数；其中第 $i$ 行的第 $j$ 个元素为 $a_{i, j}$（$0 \le a_{i, j} \le 10^{18}$）。

Print one integer — the number of paths from ($1, 1$) to ($n, m$) with xor sum equal to $k$.

输出一个整数——从 $(1, 1)$ 到 $(n, m)$ 的路径数量，使得路径上所有点权值的异或和等于 $k$。

All the paths from the first example:

• $(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3)$;
• $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)$;
• $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)$.

All the paths from the second example:

• $(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4)$;
• $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4)$;
• $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4)$;
• $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4)$;
• $(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4)$.

第一个示例中的所有路径：

• $(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3)$；
• $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)$；
• $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)$。

第二个示例中的所有路径：

• $(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4)$；
• $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4)$；
• $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4)$；
• $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4)$；
• $(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4)$。